one thing you can try is remove SSL from Exchange ActiveSync virtual directory, and make sure there is only basic authentication selected on the Virtual direcory, and then configure iphone without SSL.(stpes on how to configure iPhone without SSL is given in above KB)
Download accessmy lan and check the connectivity, it will give give better idea about issue.
https://store.accessmylan.com/main/promo-testtoolI dont think you need to aapply Sp3 for this, ActiveSync worked even with RTM, removing and re-creating vdir makes sense but first try above mentioned things.