I have a new bluetooth mightymouse with my powerbook G4. It works well BUT, it is not automatically detected when I turn it on. If I turn off bluetooth and then on again, it finds the mouse immediately.
If I don't turn the mouse off, it stays connected. ie if the mac sleeps the mouse is immedediately available when it wakes. I have not tried completely re-starting the mac.
Not sure what you mean by 'does it stay paired'. If I turn it off, it is still there in the bluetooth device panel - I made it a favourite, thought that might help but it does not.