No need of contacting Microsoft...
some considerable amount of googling on this provided a small trick that worked!..
you need to go to the accoutsummarypage of live.com and then change ur "msn ID" to something else.. (It doesn't have to be a real one). then It'll ask to verify account... proceed, then change it back to the real one.. use www.live.com to login again and click to send verification mail.. you will receive 3 mails altogether in this process...and u can be sure to receive the confirmation link in one mail once u change back the msn ID to the correct one... So, it does the trick!.. and then no longer you'll get the "email address not verified" message in front of their display names...(re-login to msn messenger after the process is completed)