@Daniel Vitek
Thank you for your detailed post!
I found a related issue answered by @Kael Yao and will post the solution shared below.
-----------------
535 5.7.139 Authentication unsuccessful:
There may be two possible causes for this issue.
Please refer to this link and check point 3 (Azure Security Defaults) and point 4 (Conditional Access policy): Error: Authentication unsuccessful
These settings would block Legacy Authentication.
--------------------------
I hope this helps!
If you have any other questions, please let me know.
Thank you for your time and patience throughout this issue.
----------
Please remember to "Accept Answer" if any answer/reply helped, so that others in the community facing similar issues can easily find the solution.