Ok, This thread was very useful, I looked into it, and tested few variations myself. Reason I was looking into it as well is that I like use my headset to listen to whatever my computer plays, however, whenever i head out i wish to use it with my phone, and i got tired of manually disconnecting it from computer so phone can connect to it. So, how it really works:
Firstly, understand that pairing and connecting is not a same thing. Pairing is pretty much a saved preset setting whenever devices can recognize each other by their BT ID and allow each other to connect to each other and use PROTOCOLS they are capable of using. Can BT devices multiconnect - yes. Can new connection demand PROTOCOL ( or SERVICE if you prefer ) which is in use by already connected device - no. So, if you want to connect it to two phones to use as BT phone headset at same time - no, BUT, if you'd play with setting and on one phone you will have only Audio Headset service enabled, and another will phone will know this device to have only Headset service - they'll work fine. First one will play music only and won't answer calls for example, and another will use this BT headset as phone headset. It can actually play audio with it too, but it will be crappy quality. And, they wont play at same time neither since they use same physical resource ( speakers in a headset ). As for my original case - it was even easier, since I just wanna use BT to listen to computer audio, i just chose it to have Audiosink service available only. So, whenever phone connects to it, it will reserve audioheadset, telephony and remote control. They are connected together now

. Use of shared physical resource ( speakers ) is switched between services requiring it ( audiosink, telephony etc) in an order of FIFO ( first-in-first-out)
Hope it helped, Cheers