@pharaoh - Madonna's Voque used a processing called "QSound" that, if I remember correctly, was relatively new back then in '89/'90.  It used (essentially) phase cancellation techniques to get that soundstage that you are hearing. 

I distinctly remember discussing this processing back in college at the time during my recording classes and I don't think it was all that popular of a processing technique since few listeners of modern pop would sit behind a decent stereo in the sweet spot to be able to really hear that processing.  I think there was only maybe a handful of albums that utilized this processing.  However, I agree, it's pretty cool.  Check out Rescue Me on Madonna's Immaculate Collection greatest hits compilation for the effect on the thunder in that track.

Listening to some Heart last night I was amazed by the sound stage of Dream of the Archer.  And it is readily available everywhere I imagine. 

Hector Berlioz, Symphonie Fantastique, Kojian and the Utah Symphony.  Reference Recordings RR-11CD.

If you want to hear a natural, deep soundstage, nothing beats classical.

Classical music is almost always recorded in such a way, that captures the natural soundstage width and depth of the acoustic space in which is was recorded. And the position of the musicians within the soundstage.

Capturing as much of the spatial cues of the acoustic space, and the musicians within it, is one of the stated goals of good classical music recording. Usually this is done using Decca tree, Blumlein, or other AB or XY mic configurations.

I doubt capturing natural spatial cues even makes on the list of goals of most rock and pop recording engineers.

The vast majority of studio rock or pop recordings, if they have any semblance of soundstage or imaging at all, it is the result of the recording engineer using studio ’tricks’, such as: panning, delay, echo, phase, etc.

In other words, with a classical recording, if the percussionist sounds like they are coming from behind the orchestra, that is because that is where they were when the recording was made.

With studio rock, country or pop recording, if a musician happens to sound like they are coming from deeper than the rest of the musicians, that’s because that is where the engineer, using studio effects, place them in the recording.

I have many classical recordings that sound as if I can get up off my listening chair and walk into the soundstage and among the musicians. I can’t think of any of my rock recordings that create that kind of soundstage.

With all that being said, my tastes in classical music tend toward he atonal, avant-garde, serial, dissonant, and overall, dark and ’thorny’ sounding, so YMMV on any of my recommendations.

Ernst Krenek - Static and Ecstatic / LA Phil chamber orchestra, Varese International label.

Donald Martino - Notturno; Charles Wuorinen - Speculum Speculi / Nonesuch Records

Elliott Carter - Three Occasions for Orchestra / EMI

Augusta Read Thomas - EROS: Goddess of the Dawn / Reference Recordings.

But seriously, I could list dozens of classical recordings with great, deep soundstage.

Pieta Brown - Freeway
Shelter Now

Peter Gabriel 
and I'll scratch yours
Don't Give UP (Fiest, Timber Timbre)