I had this same issue. Apple wouldn't help me, unfortunately. If I recall correctly, I had to disassociate iMessage from my AppleID completely, which seems to have worked. Although I still can't be sure.

I have a weird feeling the messages still aren't going through and a lot of my friends think I'm being an asshole.