In case anyone's wondering, because no-one else on Google's fine earth seems to know: yes, Microsoft's Bluetooth Intellimouse Explorer does work with Mac OS X. There are drivers on the CD (and a new version 6.0 just released for download). I'm using it on a G3 iBook with the USB Bluetooth adapter that came with the mouse - the only thing that took a while to figure out was that you have to press and hold the little button on the underside of the mouse while Bluetooth Setup Assistant is scanning until it's detected, rather than just pressing the button quickly.
Update: it works in Ubuntu Breezy too (except for the scroll wheel, so far), with a couple of commands from this forum thread.
I have a feeling that moving the mouse further away from the computer might help it to be detected, though that could just be superstition.