After purging syncevolution on my phone, clearing all sync-caches and 
configs and rebuilding the config from scratch, this error disappeared.

So it was actually a misconfiguration/bug on my phone.

You were absolutely correct with you analysis. Thanks for your help 
and sorry for wasting your time.

Your client is broken. It confirms the adding of the server event with 
a Map response, yet it sends another Add message for exactly the same 
event during the next synchronization.

So I just gathered some more data on this issue.

Here is what I did:
- I created a new calendar in horde and made this the only one to be synced
- then I started a sync (using "refresh from server") to wipe my phone 
calendar
- after that, I had just one entry in both my phone and the horde calendar
- next I created an event on my phone and changed the sync type to 
"slow sync" (btw. I tried "normal sync" before, but that did not work)
- after the sync, I had two events on my phone, but three in the horde 
calendar

Attached are the files from /tmp/sync, as well as the horde.log. I had 
set up the error_log in my php.ini, but this file was not created.

Please read http://wiki.horde.org/SyncMLProblemReport and follow the 
steps to generate complete SyncML debugging information.

syncing the calendar with my phone (Nokia N900) using SyncML in 
SlowSync mode creates duplicates only in horde calendar.

- I tried normal sync, but this failed to sync new events
- calendar on my phone is fine (no duplicates), no matter how often I 
repeat syncing
- only the default calender in horde (I sync multiple calendars) gets 
dupllicates
- not all entries are duplicated, and not the same in every run. 
Somehow looks like only the oldest (say 200) entries are duplicated. 
As a result, my entries from last year are 3x in Horde calendar, those 
from spring this year are 2x in the calendar and the current entries 
are fine (just a single entry per event)