Every time I switch between OSs (WinXP and Xubuntu) the Magic Mouse stops working, so I have to unpair the device and add it back, which is pretty annoying since I have to keep a backup mouse.
When I simply reboot the same OS instead the mouse works correctly.
Although I don’t have the Apple Magic Mouse, it happens because each installed OS on each machine has its own list of paired devices. In addition, by your description it seems the Magic Mouse can only be paired to a single system.
I don’t know if there is any bluetooth mouse that can be paired to more than one system. I’m afraid your best options might be a wired mouse or a second mouse.
BTW, I’ve read that some bluetooth headphones can be paired to multiple systems, but I never got it to work.