I'd like to add something here. I switched from Blackberry Curve yesterday and was having all kinds of issues with Contacts syncing up on my Verizon HTC Eris that I got for $30 at Best Buy. I am the Exchange admin for my company and I ended up going into the logs on the server and finding that there were issues with all contact that I had a picture associated with.
They were all for friends of ours that my wife send to me from her Blackberry (non Enterprise email) using Blackberry Messenger, long before I ever got the Eris. They sync'd with my Outlook fine back then through my Blackberry Enterprise Server, but for some reason the Eris did NOT like them.
Even though it was just a few Contacts that had pics on them, only about a dozen of the remaining contacts (out of a couple hundred) would show up on the phone - always the same ones, not in any discernable order (alphabetical, etc.), and they'd eventually disappear altogether.
After removing the pictures in Outlook on my work PC, the Contacts sync'd up just fine. I imagine that a lot of issues people are having, even with calendar and emails, have to do with little nuances like this. It's just a matter of finding which "entries" are causing the problems and finding the common denominator with those pieces.
Hope this helps someone, cause this was a pain for me that was giving my thoughts about returning the phone, which I really didn't want to do because I love everything else about it.