I just wanted to update this thread in case someone else here is having the same issue. Mailgun moved my IP to a different one that was not on any blacklists. This mitigated the issue, but the problem persisted for members registering with email addresses hosted by their ISP (for example, @shaw.ca, @telus.net, etc.).
To fully resolve the issue I had to add the following 2 MX records to my DNS settings:
Hostname: mg or mg.yourdomain.name
Points To: mxa.mailgun.org
Priority: 10
Hostname: mg or mg.yourdomain.name
Points To: mxb.mailgun.org
Priority: 10