Outlook contacts ALWAYS sync with my phone?
I stopped using the Corporate Email app that came with my Droid because of stability issues and reasons like this. I got TouchDown (AppBrain) for my work MS Exchange email and haven't looked back.

I realize this doesn't offer a solution to your problem's symptoms, but it would solve your main problem by avoiding the inferior Exchange app all together.