Hi James. If the notification was handed over the mail server successfully, then the issue is not with Gravity Forms. I recommend reaching out to the host to see if they have any mailer logs that can explain what happens with the message once it is handed over to the mail server from WordPress.
Or, you can work around any host mailing issues by using one of our three mailing add-ons, available with any Gravity Forms license: