Why does this happen?
Basically, when you pair your device, your Bluetooth service generates a unique set of pairing keys. First, your computer stores the Bluetooth device's MAC address and pairing key. Second, your Bluetooth device stores your computer's MAC address and the matching key. This usually works fine, but the MAC address for your Bluetooth port will be the same on both Linux and Windows (it is set on the hardware level). Thus, when you re-pair the device in Windows or Linux and it generates a new key, that key overwrites the previously stored key on the Bluetooth device. Windows overwrites the Linux key and vice versa.
Bluetooth LE Devices: These may pair differently. I haven't investigated myself, but this may help Dual Boot Bluetooth LE (low energy) device pairing
How to fix
Using the instructions below, we'll first pair your Bluetooth devices with Ubuntu/Linux Mint, and then we'll pair Windows. Then we'll go back into our Linux system and copy the Windows-generated pairing key(s) into our Linux system.
- Pair all devices w/ Mint/Ubuntu
- Pair all devices w/ Windows
- Copy your Windows pairing keys in one of two ways:
- Go back to Linux (if not in Linux) and add our Windows key to our Linux config entries. Just note that the Bluetooth port's MAC address is formatted differently when moving from Windows to Linux - referenced as aa1122334455 in Windows in my example above.
The Linux version will be in all caps and punctuated by ':' after every two characters - for example AA:11:22:33:44:55.
Based on your version of Linux, you can do one of these:
- Before Mint 18/16.04 you could do this:
sudo edit /var/lib/bluetooth/[MAC address of Bluetooth]/linkkeys - [the MAC address of Bluetooth] should be the only folder in that Bluetooth folder.
This file should look something like this:
[Bluetooth MAC] [Pairing key] [digits in pin] 
AA:11:22:33:44:55 XXXXXXXXxxXXxXxXXXXXXxxXXXXXxXxX 5 0
00:1D:D8:3A:33:83 XXXXXXXXxxXXxXxXXXXXXxxXXXXXxXxX 4 0
Change the Linux pairing key to the Windows one, minus the spaces.
- In Mint 18 (and Ubuntu 16.04) you may have to do this:
Switch to root:
cd to your Bluetooth config location
/var/lib/bluetooth/[bth port MAC addresses]
Here you'll find folders for each device you've paired with. The folder names being the Bluetooth devices' MAC addresses and contain a single file
info. In these files, you'll see the link key you need to replace with your Windows ones, like so:
- Once updated, restart your Bluetooth service in one of the following ways, and then it works!
- Reboot into Windows - it works!