I had all of these problems with several cheap models of bluetooth earbuds until I got some Sennheiser CX 150BTs a few years ago. They connect to both my computer and phone at the same time if they're both on, switch between the two automatically thereafter (whoever plays audio first gets exclusive use), sound decent, and get 8-10 hours on a charge.

Cons: mic volume is low, and when a device disconnects they will play disconnect sound until they reboot.