The problem with some email providers rejecting email as spam is usually caused by "SPF" (Sender Policy Framework).
SPF uses the "reputation" of the sender's email provider's IP address to determine whether or not an email is spam. As thousands of email users will share the same IP address it only takes one email user who sends out spam to tarnish the IP address reputation. Thus, for a short while, emails might be rejected as spam during the period that the IP address is blacklisted. Lots about it on the web if you want to search for it.