Since no-one has stepped up with an answer, I'm going to add a few things that may help get you (or someone else) closer to an answer.
In a nutshell, your question is about HSP - the mono headset profile and A2DP - the stereo profile.
HSP was designed for two way, low latency (delay) audio - designed for the limited spectrum telephone lines send for human voice frequencies. It sacrifices sound quality needed to make stereo music sound good.
A2DP is all about better quality and allowing different encoding schemes to get the best music over a bluetooth link (with potential interference) and sacrifices two way audio, microphone, and adds delay to queue up enough music to allow playing over momentary interference or pauses in bluetooth.
Your headset speaks both - so if you could get your headset to only advertise A2DP, the mac would be forced into stereo. I don't think it's possible, but you might see if Nokia allows you to control this.
Even if you were willing to give up HSP completely on the mac, I don't know if you can delete the driver files and re-program the bluetooth board to not negotiate HSP with your headset.
I do know you can use the Bluetooth Explorer (part of Xcode 3) to systematically clear the preferences and play around with things to see if you can really remove all records of the mono pairing. Whether you could edit the profile to delete HSP from the pairing record is hard to know unless you wanted to experiment and learn in depth how this was engineered.
Some things that will help you track the settings are in
/Library/Preferences/Audio as well as using the option key while pressing the mouse on the bluetooth menu to expose the
bluetooth link address of each device so you can match the plist files to actual devices. (Or get the developer tools and use Bluetooth Explorer)
Lastly, you might run the Bluetooth diagnostic utility to see if interference with other devices might be causing your mac to systematically choose HSP which is more nimble than A2DP.
Good luck - I don't have a device with both A2DP and HSP to test, but I can tell you that my A2DP device is by far the worst when it comes to the % of time it fails to connect. (Which is the point where you choose whether to connect as mono or stereo) I usually need three connect attempts to get it working and I'm in a very low noise environment. It works really well once paired - just hard to connect.