Matt’s right. This will also happen with AOL, Hotmail, Live, and any email service that routes messages through one of these providers.
The fix would be to use a dedicated sending IP address to avoid IP reputation issues that inevitably come up with shared IP addresses.
Some transaction email service providers, like Mailgun, are good about moving you to a better shared IP address if you ask them.