(written from a Production point of view)
The USS Melbourne (NCC-62043) was the name and registry number given to a variant Nebula-class Federation starship that was seen destroyed in the Battle of Wolf 359.  The wreck model was seen in both the 1990 episode "The Best of Both Worlds, Part II" and the 1993 episode "Emissary" It has the distinction of being the only studio model, besides the Borg cube, present in both depictions of the Battle of Wolf 359 and its aftermath. Footage of the wreck model was reused to represent another wreck at the Surplus Depot Z15 in the 1991 episode TNG: "Unification II".
In "Emissary", the name USS Melbourne (NCC-62043) was given to an Excelsior-class starship. The name and registry on this Nebula-class model was not legible on screen in any of the episodes. It was not until the Star Trek Encyclopedia was published in 1994 that it was revealed that "there were actually two Starships Melbourne [...] the first was a Nebula-class model, barely glimpsed as a wrecked hulk in the spaceship graveyard from "The Best of Both Worlds, Part II" (TNG). When the scene was redone three years later in "Emissary" (DS9), a decision was made to instead use the more detailed USS Excelsior model originally built for Star Trek III. Both models were given the same Starfleet registry number but since the Excelsior version was seen fairly clearly on screen, and the Nebula version was not seen well, we now assume that the Melbourne "really" was an Excelsior-class ship." Other than this comment, the Nebula-class ship is not mentioned in the Star Trek Encyclopedia.
In a later interview, Michael Okuda revealed that "Ed [Miarecki] made us two nearly-identical Melbourne models. I destroyed one of them to create a battle-damaged ship for BOBW2. Rick Sternbach helped with the battle damage, too. And Greg Jein contributed quite a bit of wreckage as well. The other Nebula model ended up on one of the side tables in Sisko's office in DS9. I think it was labeled "Melbourne", too."  
The second Nebula-class USS Melbourne model was seen as a desktop display in The Next Generation episodes "Future Imperfect" and "The Wounded". It later appeared as a desktop display in several Deep Space Nine episodes, most prominently in "The Way of the Warrior" and "'Til Death Do Us Part".
The apocryphal TNG short story "Trust Yourself When All Men Doubt You" in The Sky's the Limit established that the Nebula-class Melbourne was in fact under construction and intended to replace the Excelsior-class Melbourne. The Nebula-class Melbourne was the ship offered to Commander Riker. The Nebula-class Melbourne was launched early when the Borg attacked, and both ships were lost at Wolf 359.