I have same problem since Mid Jan 09, 公司其他人用blackberry ge就無事~
公司其他人用Iphone disabled SSL setting through Microsoft Outlook under Account setting, remote Outlok setting and problem fixed on their "3" iPhone.
But it did not work on my machine I bought from UK.
I think you should try and review your setting under Outlook anyway.