Tobias,
If you have access to your SMTP server and can modify its Access Control configuration, I think this problem should get solved. Based on your test results, I think your SMTP Access Control Authentication is marked for Both Anonymous and Basic Authentication. See the image below, it could look something similar. Access Control -> Authentication

I would normally expect that once I checked Anonymous Access, I shouldn't be allowed to check the button for Basic authentication. It makes no sense to have both enabled. Once anonymous is selected SMTP server sends mail in all cases of without-credentials/correct-credentials/wrong-credentials. So why should one select even the Basic authentication if they want anonymous. Microsoft should have handled this.
If you Uncheck this Basic Authentication, then I think it should start to work fine. And there won't be any impact on anything as well.
Let me know if this worked for you. On my side, I tested it and it works well for me.
sinhaa
If this post resolved your issue, help others by selecting ACCEPT AS SOLUTION or adding a KUDO.