Hi

I'm new... and read your thread... I'd suggest these (if money is no object)
SENNHEISER MXW1... they retail for "around" 499.00 :P
They sound phenomenal (can vouch for that)... but they do have a transmitter that attaches to your phone, that lets the earbuds communicate with the device. Since you're keeping the phone in your gym bag... the small transmitter could stay in there as well.
The transmitter is maybe a little bigger than a squared off pack of gum... and comes with a charging dock to charge the transmitter, and the ear buds.
Their comfortable, and for me, don't fall off at the gym.
(small details here)
The revolutionary MXW1 features unheralded wireless audio reproduction. Using the KLEER(TM) audio spec, the MX W1 delivers completely wireless stereo sound in perfect time and phase to the two remote receivers. Using a Twist-To-Fit design and high quality transducer, the KLEER(TM) audio transmission occurs with low latency and uncompromised reproduction without compression or shifting in the ear. The sophisticated and tech-oriented design is low profile and transports in a compact docking station that can charge the earbuds up to 3 times remotely.
--
addition:
I can also recommend the jaybird jb-200 .. they go for around 129. and have a microphone built in for taking calls... they're sweat resistant and sound great as well.