That... sounds like a nighmare. I've always been slightly bitter about not ever having been able to get the canonical version of my first name or first name last name combination on email services due to having a rather common name, but now I'm kind of glad I wasn't able to after hearing what people in this thread have had to deal with.
Out of curiosity, have you considered switching to a new email address? I've done so once in the past in the process of migrating from an @gmail address to an email address on a domain I own, and the process itself was every bit as slow and painful as anyone can imagine, but I feel the end result was totally worth it because now I can freely switch between providers without worrying about going through that process ever again. Just mentioning this because it seems like switching to an email on a custom domain would largely take care of the issue of random people mistakenly using your email as well.