Expanding on Menthix's post, if you create a
Google Mail account, and use that for the verification of your non-@hotmail/live/msn.com address, that would be one solution to your issues.
It is probably easier if you just use the normal @hotmail/msn/live email adresses. But that's up to you of course.