I'm in the same boat. Before I became a .mac subscriber, I had an iTunes account. It's just an account name, not an email address. This iTunes account is considered an Apple ID.
Later I became a .mac subscriber. Apparently this is also an Apple ID, though I never used it as such, only to sync contacts, bookmarks, etc.
Eventually .mac became MobileMe, so Apple ID xyz@mac.com and xyz.me.com are essentially the same ID, plus I have my iTunes account. All is well.
Then FaceTime comes along. It asks for me to put in my Apple ID and I put in my original Apple ID/iTunes account. It asks me what email addresses I want to be contacted by. I put my MobileMe address as one of them. Unbeknownst to me, it was linking those email addresses (verifying them) to my old Apple ID.
Then today iOS 5 comes out. I move my Mobileme account to iCloud, no problem. Setup my Mobileme address as iCloud on my devices, but go back and change the Store account to use the old original Apple ID.
All is well, until I decide to activate iMessage. Here is where I made a mistake, not really my fault, but I chose to use my iCloud/MobileMe account instead of my original/old iTunes/Apple ID. So then when it asks what email address I want to be contacted at, I try to put in my MobileMe, but it says that it's already in use. I'm like ***?????
So I go to appleid.apple.com and pull up my old iTunes/Apple ID account. Sure enough, the mobileme email address is listed as a verified email.
So I figure, hey, I'll just delete it here, then it should let me add it back to the mobileme based Apple ID for which it's named.
Nope, no dice. Still says it's in use. Even though it's not. Now I can't even add it BACK to where it was before, on the old iTunes Apple ID. It says it's in use on another account.
I think I can say that that right there is a bug. If I remove it off an account, it should then be available to add to another account. But that's not happening, now it's in limbo, seemingly never able to be used again.
I did read in another thread, that someone was able to get help from MobileMe support. They were able to free up the email address to be used again as a verified address for an Apple ID, but it took like 3 weeks to get resolved.
This is a total cluster f---.
I'm in IT, at least I can kinda figure out what's going on here......I feel sorry for all the customers out there pulling their hair out over this.
If Apple would just let me transfer my iTunes purchased to my MobileMe account, that would fix this. But at least fix your system of deleting verified emails from Apple iD's.......