AFTER HOURS OF SEARCHING AND FAILURES, I FOUND THE ANSWER ACCIDENTALLY LOL
All you need to do it to go to settings (https://admin.exchange.microsoft.com/#/settings) and UNCHECK the "Turn off SMTP AUTH protocol for your organization" because it is checked by default. It worked immediately after doing this (facepalm)
I hope this helps.