This is really strange world. Recently new skype 2.1 beta came out and I rushed to install it and see how it works. Now my headphones works beautifully although I'm not sure why :) Nothing except skype has changed but my stereo sound magically got fixed too.
My setup is: PulseAudio 0.9.15, bluez 4.41, Skype 2.1 beta (from official site for Ubuntu 8.10 32bit) and blueman 1.10. Skype works entirely through PulseAudio, in fact it can't work any other way.
After pairing my headphones I have one new device in PulseAudio. In configuration tab for this device I can choose the profile, either mono (and then I can use it as audio sink or source) or stereo (only sink is visible). In mono mode it works with skype, in stereo it sounds good. And I don't have to restart anything :) Although there's a twist, stereo sink is much much more quiet than mono sink, when I disconnect from skype and change my headphones to stereo at first I thought my sound got missing but it just was too quiet to hear anything.
If you're going to use blueman with pulseaudion 0.9.15 like I do, make sure you have PulseAudio plugin for it turned off (Bluetooth applet right-click -> about -> Plugins). If it is turned on as some sites on the internet suggests, it creates additional device in PulseAudio so you have two of them instead of just one and those devices could not work together anyway.
Also make sure you have
pulseaudio-module-bluetooth installed, in 0.9.14 it was statically linked into PulseAudio but in 0.9.15 it is additional package.
Another trick is that Skype is not listed in Recoding tab in PulseAudio Volume control, but
if you look in right down corner there's a combobox, select 'Streams' there and voilà, Skype is there and you can move that stream to your bluetooth headset.
So it works, I'm happy :) Have to move everything to Linux now :)