This has just happened to me despite having complex passwords and two-factor authentication turned on using the Android Microsoft Account app, rather than SMS.
The messages were all sent while I wasn't signed in to Outlook or Skype from anywhere (middle of the night, I was asleep) and there are no logins shown on my account activity. Wield.