I've tried to sync again. Previously I was using Windows Mobile 6.0 and Windows Mobile 6.1. And now my HTC PDA uses Windows Mobile 6.5.
Created a new partnership
Code:
synce-create-partnership "UbuntuDesktop" "Contacts,Calendar"
Then synced all my contact with Evolution (empty calendar, empty contacts list) and they were successfully transferred from my Windows Mobile to Ubuntu 9.10 Karmic Koala.
Then I added another contact, synced again and it was working. I played even more, and synchronization was always successful. I wish I didn't have to spend days to find out how it works
Some tutorials suggest to "Enable advanced network functionality" on a PDA, others suggest to disable it. I tried both options and it was working for me whether the advanced network functionality was enabled or not.