I've successfully managed to pair my old (12.2004) S750 with a Bluetooth headset. Is there something wrong!
That said, it's not the easiest thing to do! I called myself from another phone, answered it with the headset button and left the connection open. 5 minutes later it was still connected so that's when I hung up.

First, I searched the device and added it to Connections list. Then used Standby For Connection (or whatever it's called), then switched the headset on. A moment later pressed the main button on the headset again and 'Connected to [headset ID]' popped up in the display.

I'll see how it goes over the next few weeks, hopefully it'll be okay until a nice new phone is released.

Incidentally, the headset it the Opticom BT 20S 29.99 from Argos. I thought I'd try out a cheapo headset and see how I get on, because before long that silly handsfree cable is gonna get broke! Headset quality isn't amazing, but it does the job and might treat myself to a nice little Jabra when I have spare cash.