It seems that VersaMail can not accept an Exchange ActiveSync security policy.
However, on the Exchange side, you can delete the Default ActiveSync Security Policy. Once this is deleted, our VersaMail clients were able to sync:
Start --> Programs --> Microsoft Exchange Server 2007 --> Exchange Management Shell
Remove-ActiveSyncMailboxPolicy -Identity "Default"