Where does OS X remember previously connected bluetooth devices?

There's a question from SuperUser that might be useful for you.

In Lion, Bluetooth information is stored in different .plist file with Bluetooth prefix. For my case, I have~/Library/Preferences/com.apple.BluetoothAudioAgent.plist and ~/Library/Preferences/com.apple.BluetoothFileExchange.plist

Since Bluetooth devices need to work early in the boot process, they get stored in the /Library and only user specific items get stored in your user ~/Library file. Also keep in mind, that the recovery HD may also keep pairing information stored redundantly so you can use the keyboard and pointing device when booted into recovery mode.

So - the pairing is a little bit here, a little bit there, some pairings might even end up in the keychain on a system or user level.