I am using Windows Bluetooth LE GATT library to connect to and pair with a BLE-supporting device, D. Since D has a limited amount of storage space, if more than N Clients bond with it, then it will remove the first Long Term Key pair that was created during bonding.
Let's say that the device for which this key-pair was removed was a Windows Enabled machine. Let's call this W. The next time W attempts to connect with D, when it receives the LTK_Request_Event from W, it responds with Long_Term_Key_Requested_Negative_Reply, and W terminates the connection.
But here's where things get really exasperating. Even though the Windows BLE Stack seems to be aware of this response (because it disconnects), this does not seem to be communicated downstream to applications using the Bluetooth LE GATT library. In fact, from the application's side, a pairing request will return with "Already Paired", and does not indicate that anything went wrong. Of course, once the application tries to access protected characteristics, it won't be able to, and that, so far, is the only indication that Pairing was not successful. Even worse, the errors it receives aren't consistent. Sometimes, it gets "Unreachable". Sometimes, it gets protocol errors. Other times, it receives ABORTs.
Now, as a heuristic, I could use detection of this case as criteria for attempting to re-pair. Unfortunately, this is not ideal, since none of these errors actually imply that the device no longer honored the LTKs, and could, instead, indicate other issues, like that the device is out of range.
Is there any way to detect that existing LTKs have been rejected by the device?
Let's see what the Bluetooth specification says about this.
Bluetooth Core version 5.2, Vol 3 (Host), Part C (Generic Access Profile)
Section 10.3.2 Initiating a service request:
If Windows's BLE stack doesn't allow for what the specification mandates, it is not specification compliant, in my eyes, so please file an issue report at Microsoft.
The reason for requiring user interaction and not blindly re-bond is to avoid a situation where a hacker can simply spoof the bluetooth device address, indicate it has lost the bond and automatically re-bond without the user noticing anything.
EDIT:
The Security Manager chapter also has a table of actions to do when encryption fails due to deleted keys. See section 2.4.4.2 of Vol 3, Part H.
It specifically says when the devices were bonded before that the action to take when enabling encryption fails is to "Notify user of security failure."