I was having the Outlook 2003 / iPhone sync issue too, but just with the calendar. The contacts was working OK.
After trying all these tips, I finally did the "Detect & Repair" suggestion, and then downloaded and reinstalled (repaired) iTunes. This seems to have fixed the calendar sync problem

. I did notice that I had one LESS of the "COM ADD-INS" when I went back into Outlook's "Advanced Options." The one less "COM ADD-INS" had nothing to do with iTunes, so I'm guessing this was the conflict.
A word of advice

on the Contacts...the phone number "type" you give numbers can prevent certain numbers from syncing. Three types I noticed won't sync w/iPhone are: Assistant, Company and ISDN. There may be others, but that's what I've discovered thus far. To fix this, just alter the "type."