I have solved the issue for one of the domains. It was un-related. After getting more information from the user I found out she was using an accounting program to send the emails therefore relaying which the other server denied.
I still am having an issue with the server giving me the syntax error.
This is a client who emailed us asking for a quote and then we couldn't respond so I don't think we were blacklisted as it was not a domain we were emailing previously. Also, our domain doesn't appear on any of the blacklists on the internet when doing a quick search.