My whole office had this problem, because the system admin that was here before did not allow outside email. Here is how to have Microsoft resend the Verification email. I searched for hours, and finally stumpled across this.
https://account.live.com/verifysi.aspx?mkt=en-us&rp=profiles
-MysteryInk