is any headset not compatible with both? That's the point of Bluetooth profiles - if the devices have the same profiles, they work. Some headsets may be limited in how many devices they can be paired with, but I think most can pair with at least two.
I'd say the question comes down to the quality and features of the headset on its own. I have a Scala 500, and would not recommend it - the lack of any in-ear molding makes it always feel like it's not positioned right. I don't actually use it with my Macs, though.