Hmm, after some more testing I found that the problem seems to be not in the GetPaired but in the Pair method:
if (!IsPaired(mRadio, mDevice))
mDevice.Pair(mRadio, PairingCode);
System.Diagnostics.Debug.Assert(IsPaired(mRadio, mDevice));
The assertion always fails in the above test code.