I can believe it. I posted already about my experience with the free tier of Mailgun's service. I went through all their instructions about setting up the service and verifying my domain etc. but still had a lot of email rejected, especially by yahoo.com but also hotmail.com due to poor reputation IPs
Gmail.com typically delivered everything.