kernel[0]: [SendHCIRequestFormatted] ### ERROR: [0x0411] (Authentication Requested) -- Send request failed (err = 0x0006 (kBluetoothHCIErrorKeyMissing)) 
kernel[0]: [SendHCIRequestFormatted] ### ERROR: [0x0406] (Disconnect) -- Send request failed (err = 0x0012 (kBluetoothHCIErrorInvalidHCICommandParameters))

After some trying I've had success in pairing it with Remote Buddy regardless. This worked: 
1) Pair using Remote Buddy's Setup Wizard. Doesn't complete because of authentication issue above. 
2) Quit Remote Buddy. 
3) Wait for the remote to stop trying to pair 
4) Pair using Remote Buddy's Setup Wizard. 
5) Success. 
6) Reboot.

From early tests, I don't see anything I could do to work around what looks like another internal OS X Bluetooth stack problem.

Here's hope the Bluetooth stack of OS X 10.8.3 will be closer to the one of OS X 10.6 in terms of stability and reliability. We'll have to wait and see.

Best regards, 
Felix Schwarz