Loved mailgun when I was using it a few years ago for some small campaigns. Unfortunately the free tier service had a big problem with server reputation. A noticable amount of emails were spam-flagged or rejected by recipient systems.
Not surprising that free services would be abused, but was a little disappointing. I would assume the paid customers get servers with better reputation/history.
I had the same issue, sent an email to support and they moved us to a different node/cluster/whatever immediately. I’ve never had another problem on a free or paid tier.
This problem doesn't seem to be limited to free services or smaller companies. Mailing list stuff sent via Mailchimp often gets caught by my spam filter, and many Mailchimp IPs are on various blacklists used by spam filter software.
Not really surprising when some companies surely are using services like Mailchimp to send spam - depending on your definition of spam.
I was already angry enough when mailchimp merged mandrill with its main service