I noticed, about a month ago, that whenever I would log in to Windows Live Messenger, I'd get a little toast popup telling me to verify my email address:
I clicked, I followed the verification process, and I thought everything was cool. Not so. The prompt kept coming up. On subsequent times I tried to verify my address, though, it would tell me that I didn't need to verify. What gives?
I had recently taken advantage of the "linked ID" feature of Windows Live IDs. The misleading thing here: I did need to verify an email address, just not the one I was signing in with. Curiously, signing in with the other IDs didn't prompt me to verify... but that's neither here nor there. After fighting my way through support for a month on this (and specifically asking them if it had to do with my linked IDs), it came back that, yes, it was something to do with one of the other accounts.
Anyway, if you're getting prompted and you recently linked your IDs, it's probably a problem with one of the linked accounts. Make sure they're all verified.