Outlook Account Spamming

I am the long time owner of a Hotmail (then outlook) account. I noticed the other day that my emails had been sending mail that I didn't order or type what so ever. Upon looking closer it was sending messages to what appears to be all my contacts. The message said something along the lines 'hey [name] Losing weight has been made easy http://womenshealth.com-garciniacambogia.net/october'. I have never in my life been to or been related with this site or company, and have never given my account information to anyone. I am afraid that my outlook account has been somehow compromised. I have immediately changed my password in case that is the problem. I don't believe that Microsoft have the rights to use an account to send spam like that, and if they did I would be very surprised. Already I have had several complaints from people about being sent spam, including officials I know like Uni lecturers and several companies I have sent/been in contact with in the past. Is this a potential account compromise or something else? I have never had email/account problems with Microsoft before so if this is a somewhat uninformed question, sorry.

I was looking for a direct link to support via a ticket or something similar, and for the life of me couldn't find it (no other options were appropriate), if there is something of the type please, a link would be great. 

Thanks for all the help