One thing I love about pc gaming is just how long the lifespan of a game can last. Someday I'll have to track down copies of those older games with hardware-accelerated headphone 3D to get a full experience... Perhaps the continued Console stagnation will continue to bring back mainstream PC Gaming for games other than WoW, runescape, and Starcraft. Which FPS would you recommend first as a first-rate sound experience: BF2, BF 1942, or something I'm not even aware of? Have you tried Metro 2033 on PC?
Generally speaking, any game that uses DirectSound3D or OpenAL will have proper positional audio, which covers most releases from 2006 and prior. I just happen to prefer stuff like the earlier Battlefield games and Unreal Tournament because of my tastes in FPSs. (It also helps that BF2 and BF2142 were designed with the X-Fi DSP in mind in addition to using proper 3D audio APIs, as the highest sound quality settings can't be enabled without a proper X-Fi card.)
Other games like Counter-Strike would probably benefit even more from proper positional audio just due to the nature of their gameplay, but I never really got hooked on CS.
Also, if all the other people still playing it weren't so curb-stompingly good, I'd try out Descent 3 in multiplayer some more. The first two games were DOS and didn't support 3D audio (I don't think the DXX-Rebirth and D2X-XL source ports have even bothered implementing it from what I can tell), but the third one does use DS3D. It's only fitting that a game with actual 3D, 6DoF gameplay would have some 3D sound to go with it.
If we weren't talking multiplayer FPSs specifically, then the Thief series sets the benchmark for sound design and positioning in video games, in no small part due to how sound is so integral to the gameplay. Do note that all are DS3D (need ALchemy) and that some versions of ALchemy will act up with 1/2 or Deadly Shadows, while other versions work perfectly fine with both. (Thankfully, the ALchemy version included with the X-Fi Titanium HD's drivers falls into the latter category.)
I'm just glad that I'm not the only one to notice that the recent Battlefield games (from Bad Company 1 and 2, Medal of Honor, BF3) are quite lacking in positional cues. It's really a damn shame because the sound quality is absolutely among the best I've heard in a video game.
One of these days, I'm going to have to show you first-hand what Battlefield games USED to sound like, even if you'd never play those entries in the series due to the simple matter of all of them being PC-exclusive. (No, BF2: Modern Combat is not the same thing as BF2 on PC, before anyone asks.)