I always had a similar problem with my zune. It worked great everytime i got a new set for it, then after some use it would go down hill until i replaced it once again.
I am actually using the earbuds that came with the epic currently. they are great! The previous earbuds had a bad wire where it went into the mic. I have my eye on a set of klipsch earbuds when i am feeling a little richer.
Do you have a old set of ear bud or head phones to plug into it to see if maybe it might be the jack on the evo end? That might be a good start. Or ask to try some one to try their ear buds in your phone. and see how it goes!