i dealt with this in the original mydoom epsiode. i was getting back mailer daemons saying my emails were bouncing. since i'm pretty on the ball with virus crap (never been infected) after doing my legwork i knew it wasn't me. the kicker was the returned mail (with text) showing what the message was.. it had included the name (and ssn) of someone i knew who had me in his book, so i gave him a heads up. after a few days it all went away.
so yeah, your isp is in serious need of a clue - or at least the people you spoke with. i have rr myself, but i didn't need them to resolve this.
good luck tracking down the person who has you in their addy book and is infected. all it takes is a little break to figure out who it might be.