ExchangeLabs seems to support the iPhone via ActiveSync for Mail, Contacts, and Calendar. You still have to accept the invalid SSL certificate because the DNS settings are not right and then type in the server name manually. Just change the server to m.exchangelabs.com.
Once you have it set up you will be able to see and manage your calendar and address book. You will be able to search the ExchangeLabs directory. All of this is done over SSL so your communication is safe even at Starbucks. And if you loose your iPhone, you can go to the ExchangeLabs web site and remotely wipe your phone.
The only weakness is that the iPhone only supports one Exchange account at a time so if you already have an Exchange account, you cannot have two. You would have to configure one as IMAP/POP3 without support for calendaring and email.