first off: you should never have to restart your Mac for a second, 
third, .. attempt. Restarting Remote Buddy should be sufficient to 
give you back a "clean" environment for further Bluetooth tests. I'm 
not sure if this also applies for activate/deactiving the Bluetooth 
receiver. It should, it really should, but all of the Wii code is 
still to be considered highly experimental, so I can't give any 
guarantees here.

Plus, because it just springs to mind: I noticed that sometimes 
pairing will need a couple of seconds - sometimes even beyond the 
point where the "press 1 & 2" prompt disappears.

I'll try to grab a Bluetooth USB dongle for the iBook G3 and the 
PowerMac G5 next week to see whether it could be a timing issue or 
its a general problem.

Best regards, 
Felix