It's been around a month now that I've had to check spam folders for messages coming out of iOS devices setup with SMTP for sending from my provider.

It seems something might be wrong with the IPV6 lookup? A reference: https://discussions.apple.com/thread/6688173