May (will) sound silly but to clean them, I always put my earplugs in the pocket of my trousers, and throw it in the washmachine to get rid of the earwax. They really sound better after drying. 😛 And these are high quality earplugs.
However, headphones will probably not fit into your pockets, but if you've lost all hope and you're irritated enough to buy a new pair; if your headphones don't contain any watersoluble material like paper/carton, you can try and put them in the wasmachine, covered in a piece of cloth.