The headphones are able to connect once after disabling and reenabling bluetooth in Windows. If the problem were that the headphones are configured to use a fixed, predictable long-term key, it isn't obvious to me why Windows would accept that key sometimes, but not all the time.
(Note that I don't need to have Windows forget the device and re-pair from scratch.)
Is there some aspect of initial bluetooth negotiation that would explain this?