My client felt similar, the owner of the company had a Palm and had to wait and extra week for me to get his palm working. All the WM6 and iPhones worked out of the gates. It sounds very unlikely that the Exchange team would be willing to go to the pains of getting the necessary certificate and lowering their security settings (removing the Exchange active sync mailbox policy).
I think your only possibility is to see if you can set it up with POP3 or IMAP instead of Activesync.