I also have the same problem, about 2 weeks ago it just stopped working for no reason.. I've been searching all over for a solution and thus far nothing...
I have about 5 aliases setup in my outlook.com account, from which I send mail ... I can receive mail from all of them, and send normally from all except for one, a gmail account... not sure if your aliases are "gmail accounts" or not, but mine is, so I suspected the problem was maybe there ...
I did the same of removing and re-adding the faulty alias, but didnt solve the problem. I also checked in my gmail account to make sure that Microsoft/outlook was granted access to Gmail, and all seems correct (microsoft has access to read, compose, send, and permanently delete all your email from gmail) ... but still it wont work.
when I send a test email from that alias (in outlook.com), it just stays in the drafts folder and doesn't get sent. When I do it form the outlook app, it is marked as sent, but doesn't really reach the recipient. and If i check back in outlook.com, it doesnt show in sent folder.
After a while I get an error in the draft mail saying "you dont have permission to perform this action". So I suspect it has to do with that..
I found this in google forums and I believe that might be the cause, but so far I havent been able to get hold of any customer support to help on the topic.
https://support.google.com/mail/answer/7126229?hl=en&sjid=2804372637536619706-EU" To keep your account more secure, Gmail no longer supports third-party apps or devices which require you to share your Google username and password. Sharing your account credentials with third-parties makes it easier for hackers to gain access to your account."
this is pretty frustrating, if anyone has an update / solution please post it!
thnx!