While reading on the web about OSX bluetooth I came across an article talking about resetting the bluetooth module.
Pressing Shift+Option keys and clicking on the Bluetooth icon on your top bar, now displays hidden debug menus.
This menu has a few interesting options, “Reset the bluetooth module”, but the one fascinates me more is referenced below “Factory reset all Apple connected devices”.
Previously we used a GSX tool to do this, however not everyone has this option.
I have tested this on Sierra, and judging the age of the article it should work on El Capitan too.