Hi Malte,
What db version is this? Is it the latest minor release?
How often are you running 'vacuum full'?
The postgresql Bug 2379 'Duplicate pkeys in table' thread discusses a somewhat similar problem. The db has many inserts over a short period of time, resulting in an occasional duplicate key. There is speculation that VACUUM FULL may be breaking[1] (presumably during a busy session).
In my limited understanding, I beleive some of the diagnostic questions and comments in that thread might also help in this case.
1. http://archives.postgresql.org/pgsql-bugs/2006-04/msg00066.php
best wishes,
Torben
