This may be a by-product of having a PDA and Activesync so long...I had a similar problem but I use vista, and I didn't mention my sync errors because I cleared those up (i think) but the contacts/birthdays I was getting a sync error with happened to be a contact that I have had since my first PPC...
heres the thread I started...
http://forum.ppcgeeks.com/showthread.php?t=60941