Update: The messages stopped which is nice and I also could pinpoint the issue of the missing mails: They are stuck on a mail gateway because the sender address is not right.
Let me elaborate: Because of some awesome ticket system we need to set a lot of different email sender addresses in our notification rules. For some reason Checkmk sends these mails with the fallback sender address ($SITE@$HOSTNAME) of the appliance, rather than the specified address. What is even weirder is that some rules seem to work correctly. This behavior started right after the upgrade to 2.0.
I am going to enable better logging and try to understand why this happens.
Will update here as soon as I got information.