Guys, thanks a lot for the bunch of recommendations and opinions - I have a lot of material to go through, and after seeing some of your proposals I am even reconsidering my requirement of the earpiece to be wired.

Some of my first findings are related to the WH-205 and WH-701, which seem to have a good reputation when it comes to sound quality, but at least most of the reviews complain about extreme fragility, which makes me think they may not be suitable for running or sports in general.

The AD-54 is a very cool little thing. The few reviews (Amazon) I have read praise it extensively and it is inexpensive enough to give it a go.

Next I'll dig into the bluetooth suggestions. The bluetooth has the plus of not having problem with the custom Nokia pin setup - also some of the models you guys have brought up look really nice.