One of the unexpected casualties of the iPod age is banded, in-ear headphones. Sony used to make a set that really suited my ears, but they did not lend themselves to lazily twining around an MP3 player and throwing in a pocket. I've come around to ear buds, especially the higher-quality Bose and Sennhauser models, but I still find them hard to keep in the ears... there seems to be some sort of casual cocheal queefing that occurs that makes even the best ear buds plop out at the most inconvenient times.
Perhaps it's simply an issue with the rubbery shape of most ear pieces. Acoustibuds offers threaded, snap-on pieces for most ear buds, and they boast improved fit and sound quality due to flexible, hypoellergenic fins and a twin-cone core design. Who knows if they actually do help keep ear buds in your slicked, greased up aural canals, but my instinct is that anything with ridges probably would, and if they can make those ridges comfortable, it's worth a shot, especially for $13.