This is the only working solution for me. Enjoy.

My symptoms:
– Previously working bluetooth speaker (UE BOOM 2 in my case) stops connecting
– Windows 10 ‘Bluetooth and other devices’ menu shows the device as Paired
– Pressing connect makes it attempt to connect but fails then it goes back to Paired
– Remove device hides the device from the menu, but as soon as you turn bluetooth on and off, or restart the computer, the device comes back
– You pull your hair out.

Solution that worked for me after much, much unsuccessful internet trawling and one system restore:
– Download this 7 year old command line bluetooth toolset: Bluetooth command line tools – work with bluetooth from the command line
– Install it, make sure you enable the option to “Add Bluetooth Command Line Tools directory to path”
– Open Powershell
– Put your device that isn’t working properly into pairing mode
WARNING: THE FOLLOWING COMMAND WILL UNPAIR ALL BLUETOOTH DEVICES
– type in “btpair -u”
– Boom, all of a sudden Windows asks me if I want to allow pairing to my device that isn’t working
– Hit yes, successfully connected again
– Cry tears of joy

God I hope that helps someone else.

Credits: xzion .