Well I uninstalled the antivirus and that ended up causing more troubles (exchange doesnt like not having antivirus and the information store service wouldnt start because of it). So I reinstalled the antivirus and made the 2 registry key changes:
You might want to enable Pro Active Scanning and Back ground scanning on the mailbox server by looking at HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\MSExchangeIS\VirusScan reg key.
You will have to change the values for "BackgroundScanning" and "ProactiveScanning" to 1 and restart the Information store service.
And low and behold everything started working. My iPhone started receiving email (unread ones as well!) and when I did a manual sync on my Windows Mobile alll the email came through. So I will continue testing it for the rest of today and tomorrow to ensure it is working correctly.
I guess one other question, a bit off topic: can windows mobile receive emails instantly via push or is it only every 8 minutes?