Unfortunately, unless you're paying for a dedicated IP address with Mailgun, their sender reputation is mostly quite bad. We are constantly having to request our account to be moved to a new IP due to them landing up in some blacklist.
If you are seeing continuous problems, I'd love to take a look! My email address is on my profile.
Mailgun will do some chores for you, for a fee. If those chores are things you can do in your sleep, fine! Mailgun does nothing magic.
In the case of Mailgun, you should be assigned an IP with a neutral reputation. For example, before dedicated IPs are reassigned we leave them dormant for at least a month, usually much longer, before assigning to a new customer.