Short version
I had some long forgotten SMTP clients (in-home IP security cameras) that kept failing logins to Outlook.com's SMTP server every minute! So outlook.com would periodically block all other email clients from connecting from my home's IP address, even with the right password, leading to the problem in the question.
Interesting but long story
I had IP security cameras setup to email me on some events. Those were setup to login and send email via SMTP and they were using my username@outlook.com + an old password. They are essentially "SMTP" clients but since they are fixed to the ceiling and outside, "out of sight = out of mind".
Yesterday, Outlook.com's login page (finally!) hinted that I was having too many wrong logins, so it wanted to verify if I'm a human (usual mangled text image). That was a clue, so I logged onto https://account.live.com/Activity and noticed that there was a failed login almost every minute (= 10,000 failed logins per week since who knows when!!). Even more surprising, the source IP address for all logins (failed or successful) matched the external IP address of my router. So either someone hacked into my WiFi or was spoofing my IP or my one of my email clients was just nuts.
I disabled Outlook.com email on my iPad, kept iPhone off my WiFi (only LTE) and kept Outlook 2013 as-is overnight. Still saw the weird failed logins at https://account.live.com/Activity so logged to my router (Apple Airport Extreme) to see if I had any suspicious WiFi clients connected. None, but I did notice the WiFi cameras and then it suddenly hit me that many months back I had setup SMTP notifications on the security cameras and I had changed my Outlook.com password in the last few weeks but had forgotten to reconfigure the security cameras!
I reconfiguring the security cameras for the new Outlook.com password (happened to be an application password since I now had two factor authentication) and sure enough, the IP camera sent me an email about the there being a reboot event sometime back. I have no idea how long the camera was attempting to send out that email (it was last rebooted a while back) but it had been trying, every minute for quite sometime effectively mounting a DoS attack on the rest of my email clients (by triggering a security response on the Outlook.com authentication servers).
Anyway, now everything works very well and I'm happy that this was my issue an not a Microsoft Outlook.com issue.
Microsoft has built a fantastic product with outlook.com and it worked exactly as expected. One suggestion would be to notify the user of 3+ failed logins on the next browser login AND putting a link to https://account.live.com/Activity right below that notice asking them to review that list.