Make absolutely sure the webcam isn't in use. Check your running processes in your Task Manager. Especially those (quite often very unneeded) processes which are always automatically loaded from the \Software\Microsoft\Windows\CurrentVersion\Run registry keys.
Some programs load themselfs in the background (to start up more quickly) when you start Windows. Your webcam tool/utils program might be one of them. Other programs, when they are loaded and use your webcam, do not completely release the webcam, eventhough you exit the program.
I have come across quite a lot of such programs and video tools.
Video call works in a slightly different way.
Now, I'm not saying there isn't something wrong with Messenger and how it connects to the webcam, but the above should certainly be checked out first.
If all else fails, contact support:
https://support.live.com/default.aspx?productkey=wlmessenger
If the above link brings you to https://help.live.com/ instead, then choose any topic > click on bottom right link "Get more help" > click on link "Get support"
/ 
