We had issues every few months because the server we were assigned would be added to a RBL. Customers would notice, we'd talk to Mailgun and they would move us to another server. rinse, repeat.

The only way to avoid this was to get a dedicated IP which is an additional $59 / month.

I'm not sure why Mailgun couldn't detect this themselves, maybe they do now.