From my personal experience with Bluetooth devices in general: it may be a matter of Pairing, not to be confused with Connecting.
In a metaphor that has just come to me: being Connected is being together, being Paired is wearing the other's wedding ring. (Note that Bluetooth has a master/slave-architecture. Headphones can be a slave to one master only.)
Me, I have quite some Bluetooth audio devices, due to the problem that you describe. If possible, I keep headphones Paired with master devices, whether Connected or not. If I know that I may Connect these headphones to other masters, I Unpair them before Disconnecting.
Unpairing may be a matter of pressing the Bluetooth button on the slave device for a "long" time. That's my trial and error.
Hope This Helps...