I know this seems obvious, but i want to mention it just in case that's it...
I had to struggle with this problem for a few days, just to find out that the problem was spam filters.
Some mail services require a certain set of headers, including what user-agent was used and other redundancy...