Hello mate...I went through the same thing for about a week when trying to find mine (which I got from o2 store on Fleet Street, yay!
Option1. Go to your local o2 store and ask them to search regional stores to see if any of them have stock left. They checked about 4 or 5 stores near my place of work and home, only the Fleet Street store had one they were happy to part with. Most of the stores that have stock left are keeping 'em for staff, t0$$er$.
Option 2. Google it - buymobilephones.net/mobile-phones/HTC/HTC-Sensation-XL-Free-Beats-Solo-HD-Headphones
Hopefully that will answer your question!