Ironically, I am NOT trying to pair a device. In fact, I have a paired Microsoft Keyboard at work, but when I take my laptop on the road, I don't expect it to be paired to the keyboard (500 miles away, duh).
Just recently and without any config changes to my bluetooth radio, I have started getting a message in the system tray from the bluetooth icon saying "Error pairing with device Microsoft Keyboard" when I am on the road.
It's really annoying and I don't know how to stop it, and I can't figure out why after two years with the same configuration this has started happening.