@ Age
In the email log, does it say it was sent successfully? If it does, then there is not much I can do at that point. It is there that the email is handed off to the email server to send. WP basically just reports if that was successful or not. It is the job of the email server to send the email and that is beyond the control off WP and Connections.
If your web host provider has email logs, perhaps they can shed light on to it. If you are sending the notification to a Gmail address and the To/From are the same and the address is actually an email alias for another email address in Gmail then Gamil will ignore the email. I think… there is some combination of settings where Gmail will not receive an email.
Not sure if this helpful, but I hope it does help. Let me know.