Bluetooth Without Tethering

Okay, this one is a bit annoying. I have two PCs I regularly connect to using Bluetooth (mainly so that I can use LibreOffice remote, etc). My main PC connects just fine. The other PC will connect but only if I turn on tethering. I have no idea why and I don't particularly wish to tether as I don't actually want to use the internet on the PC, I just want to send commands to the PC via bluetooth.

Does anyone have any idea why it keeps demanding tethering in order to work? I did a search but I only turned up responses from people who had the opposite problem and wanted to tether.

Does the PC in question support Bluetooth discovery mode? This might be the problem.

How would I check?

The PC can certainly find and be found by my phone. I tried on a 3rd PC and got the same issue. One was running XP and the other Windows 7 so it's not just an issue of the particular OS on the PC.

As I said, the PCs will connect quite happily as soon as I turn tethering on, but I can't figure out for the life of me why that is an issue. I'm running 10.2.1.2102 in case it's an OS issue with the phone.