Is there any kind of spam report attached to the email? It might tell you if the server it was sent from is listed on a spam blacklist. The recipient can try to "examine the headers" of a "spam" email in their mail reader and see what it says. If your server is blacklisted, open a support ticket with all the information, and support will try to get the server cleared off the blacklist. What is the nature of the emails? Do they contain lots of links, or a number of terms typical of spam? Are you blasting out large numbers of emails at once? Any of those could get it treated as spam. The recipient may be able to "whitelist" your account to have your emails treated as non-spam.
If all else fails, open a ticket and ask if they can check spam blacklists for your server. They might not be able to do this without specific information (from the headers) of which list it's on, but it's worth a try.