These Emails aren't in my MSN contacts list, nor have I ever emailed them before
Can I ask you something without sounding too stupid?
Do you have protection of some kind, for example anti-virus and firewall? I'm asking cos I could see one of the icons in the Task Manager which is red with white cross on it. That mean Windows has detected there may be something wrong with your PC's security.
Last year some web-based email services were targeted and many people got their password hijacked - yahoo, hotmail, gmail etc. More on: http://news.bbc.co.uk/1/hi/technology/8292928.stm
I would recommend change your password ASAP, run anti virus and use firewall (if you don't have them). There are couple of good free anti virus and firewall programs.
Hope this helps