I don't have experience with Paid Memberships Pro, but it seems unlikely that email problems would impact on it. I wouldn't want to use a payment system that relied so much on email if it did!
Are you sure that the payments are going through (ie is the money actually reaching your account?) I did some quick Googling* and it seems that Paid Memberships Pro can automatically downgrade a membership if the payment failed at the Payment Gateway. There's also something at the bottom of this page about Paypal Express, that if the user completes payment at Paypal but doesn't click back to your website, they might not actually have an account made for them yet:
https://www.paidmembershipspro.com/o...iptions-pmpro/
Again, I'm not familiar with Paid Memberships Pro so I might be sending you off on a wild goose chase here. But maybe if you can see the Order Status on those orders and compare it with the link above, it might give a hint on what's going wrong.
(If it is related to email, I've successfully switched the email on one of my FQ domains to a dedicated email host, so I might be able to give some tips - but I don't think this one is related to email.)
*(Actually Bing-ing, but that sounds too much like I was watching Netflix, am I the only one left using Microsoft Bing?....)