test your spf records, apply for microsoft senderid, and try domainkeys...
also make sure they login through their domain server for the smartermail server like mail.domain.com if from@domain.com ... not mail.other.com (thats often the case)... make sure they use their login and password...
turn off relays... see if that helps too.
these are good tests accounts as well:
dktest@exhalus.net
check-auth@verifier.port25.com
spf-test@openspf.org