If someone is telling you they aren't getting your emails, or they are being marked as spam try the following.
1) Check that you are not on a blacklist and if you are go through the blacklist owners process to get yourself off it. (http://www.anti-abuse.org/multi-rbl-check/)
2) Ask the recipient to check their systems to ensure you aren't listed as a spammer
3) Ask the recipient to whitelist you in their IT systems (services, servers and end user apps)
4) Setup SPF records (http://en.wikipedia.org/wiki/Sender_Policy_Framework)
5) Setup Domain Keys (http://en.wikipedia.org/wiki/DomainKeys_Identified_Mail)
6) Send emails in plain text only (set the default type to text only when composing a message)
7) Remove any links from emails
Items 4 and 5 will only work if the recipients email systems check these before accepting delivery(4) or allowing the message through to the user(5).
Once you have the problem resolved you can try going back to HTML email with links if you need to.