Does the iPhone's Active Sync Rely on IMAP Support? (Currently, I have it blocked) Is support better in Exchange 2007 or Exchange 2010?
What are the minimum requirements to set up an Exchange Server to play well with iPhones?
ActiveSync doesn't use IMAP. ActiveSync is a "protocol" unto itself (HTTP / HTTPS-based).
Exchange 2003's ActiveSync implementation, provided you've installed Service Pack 2, will work fine with iPhones (I've got several Customers doing it).
Assuming you've got a single Exchange Server computer you'll need to allow access to port 80 and 443 from the Internet to the Exchange Server computer (port-forwarding in your firewall, etc). To make life easier you should purchase a third-party SSL certificate for your server because you won't have to muck around with certificate trust issues (albeit on the iPhone it's fairly easy to make a self-signed cert work).
The Microsoft Exchange Server Remote Connectivity Analyzer is a good tool to test your ActiveSync server. There are some client-based ActiveSync testing tools available, too, but I've never used any and can't say how they work (one is available at https://store.accessmylan.com/main/diagnostic-tools for example).
If your Exchange Server has been up awhile and has exhausted its named properties quota you may have trouble getting ActiveSync to work until you increase the quota. If you're not getting repeated event ID 9667 events then this probably isn't a problem for you.