I have used cheapo sub-$20 SoundBot headphones for almost a year and a half now, and have literally never had an issue with wireless connectivity.
EDIT: Ah, throwanem (https://news.ycombinator.com/item?id=13170546) points out the crucial difference between headphones and earbuds. For me, earbuds are undesireable, so I didn't realise that the form factor was meant to be a selling point.