Mark, DomainKeys seemed to increase the "chances" of going through. After installing DomainKeys we got a lot of messages (compared to none before) to go through, but then all of a sudden they started being sporadically blocked again. We do know that the DomainKeys is working because test emails that did go through show a "DomainKeys verified that this email came from domain.com".