I’ve got the same issue with Mailgun. Different host, so it isn’t that!
I wonder if there is a problem with the Mailgun config instructions for VERP setup: