Telus / P4000 user here.
Telus has a rebate on Jabra BT320 wireless headphones that basically makes them free (well, if you can call anything free that includes a 3-year contract with mandatory data plan).
http://www.e-katalog.ru/jpg_zoom1/55428.jpg
Anyway, the Jabra wireless BT receiver allows you to plug in any (e.g. iPod style) headphones.
The sound quality is okay, and the volume is not as loud as the HTC stock headphones, and the wireless is a bit testy... but overall they are not too bad.
Also, I like the idea that I can connect the Jabra receiver directly to a friend's stereo or a newer car stereo with a 1/8th-inch cable and play DJ wirelessly.