My $20 totally off-brand bluetooth headphones support multi-pairing. Does it always work 100%? No. Do I think cheap multi-pairing capable headphones will get a lot better as it becomes more important? Definitely.
What do you use? I also buy $20 totally off-brand Bluetooth headphones (I wear them while exercising, and sweat ruins them every few months), and mine don't have this feature, which I would love.