Lost rows / corrupt data?

Hello,

We have a long running DB application using PG7.4.6. We do a VACUUM FULL
every night and a normal 'maintenance' VACUUM every hour. We do nothing with
any indexes. Every now and then we get errors from the database whereby an
update will fail on a table saying that there is duplicate violation on a
primary keyed row. Theoretically this is impossible as the constraint should
prevent any duplication, ever. When the next vacuum is run, we see an error
saying that there are more rows than the database can account for (or words
to that effect) and we should either REINDEX or TRUNCATE the table.

Firstly, how and why could this be happening, and above all how, do we
prevent it.

Thanks and regards,

Andrew.