Bluetooth devices identify themselves using a 48-bit hardware address – almost exactly like the Ethernet MAC address. It's baked into the hardware, and unlike Ethernet you cannot change it easily, since the Bluetooth address is used for authorization and for picking the right encryption key.
When dualbooting two operating systems, the hardware address stays the same, but the systems store link keys in different places, which causes great confusion when a device is paired with OS A and you try to use it from OS B. Having to redo pairing on every reboot is not fun.
Fortunately, the link keys are just 16-byte-long pieces of random data, stored in plain – BlueZ keeps them in a text file in /var/lib/bluetooth, while Windows uses the registry location HKLM\.
By default, Windows only permits NT AUTHORITY\SYSTEM to access the keys, since user programs should never need them, but an administrator can add themselves by browsing to the place in regedit, right-clicking on the Keys key and choosing Permissions.
After that, keys can be exported with regedit or reg export and massaged into something BlueZ can understand. The reverse process is possible as well – Windows will notice new keys immediately, no reboot required.
Example of an exported .reg file:
Windows Registry Editor Version 5.00 [HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\BTHPORT\Parameters\Keys\a1b2c3d4e5f6] "0ab12cd34ef5"=hex:ac,79,e3,ec,08,a2,2f,a1,06,25,83,8e,65,ce,55,63 "0013d4f42bc4"=hex:30,64,4e,16,1e,eb,46,74,4d,b4,d1,93,cd,00,d4,ac
The corresponding BlueZ 4 file is /var/lib/bluetooth/A1B2C3D4E5F6/linkkeys; its format is simpler (although I don't know the purpose of the other two fields, but I guess they correspond to "PINLength=" and "Type=" below):
001FE46789AB AC:79:E3:EC:08:A2:2F:A1:06:25:83:8E:65:CE:55:63 0 4 0013D4F42BC4 30:64:4E:16:1E:EB:46:74:4D:B4:D1:93:CD:00:D4:AC 0 4
BlueZ 5 uses a keyfile-like /var/lib/bluetooth/A1:B2:C3:D4:E5:F6/00:1F:E4:67:89:AB/info:
[General] (various settings) [LinkKey] Key=AC79E3EC08A22FA10625838E65CE5563 Type=5 PINLength=0 [DeviceID] (more settings)
Also pay attention to the Type= setting. I think this specifies the encryption algorithm used between devices – my 2011 tests with a Bluetooth 2.1 device used type 4, while nowadays I see type 5 after pairing my new phone. I also haven't looked into where Windows stores this information yet.