If all else fails and you want potentially better customer support, I would give SendGrid a try. I have had very good results with them. In a similar case, someone from their tech support spent over an hour on the phone helping us sort the issue out. And it was a mix of things, configuration, etc