Short update on this problem, which should be fixed by now: - I was able to reach the responsible team, and they answered very quickly. I was positively surprised! - They confirmed there's a problem with the zone content on their Dyn nameservers - They then added additional NS records on level msa.msidentity.com to point only to Akamai servers (overriding the 50:50 split for msidentity.com) - The result now is that mail.msa.msidentity.com gets resolved only bei Akamai servers, and should thus resolve reliably.
I don't know the reason why they couldn't just fix the zone copy that gets distributed to the Dyn servers, but the workaround fixed the problem at hand, so problem solved :)
Congrats to the Microsoft AAD Network SRE team, I didn't hope to get any answer, but they took care of the problem right away!
Cheers, Markus