Hi Dawid,
Great to know that the issue has already been resolved and thanks for sharing the solution so that others experiencing the same thing can easily reference this! Since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others", I'll repost your solution in case you'd like to Accept the answer : )
--------------
Issue Symptom:
Got an error message “530 5.7.57 SMTP; Client was not authenticated to send anonymous mail……"
Resolution:
Caused by allowed only specific IPs from MS and it turns out after allowed everything that mail began to flow again.