You might want to look into your email server logs.
I would imagine it would have to be because of the email failing to be sent by the email server. Since you get some emails it would seem that the scripts that tell the email server to send the email are probably all working, so it would have to be that the email server isn't sending the email, or the emails are getting spam blocked and are being sent and you just aren't receiving them.
I doubt it has anything to do with express checkout directly.