Yipes, I'm getting bit by duplicate tuples

I've got a production application (currently running on 6.3.2 + Btree
patch) in which several clients concurrently update the same set of
tables. The client requests are pretty simple --- SELECTs using
btree-indexed fields, INSERTs, and UPDATEs. Updates are always of the
form "UPDATE table SET some-fields WHERE id = constant", where id
is a unique identifier field with a btree index. (Some of the tables
use OID for this, some have an ID field generated off a SEQUENCE
object.) We never delete any tuples. We use BEGIN TRANSACTION / LOCK /
END TRANSACTION to protect groups of related updates.

What we're seeing is that under load, the tables occasionally get
corrupted by duplication of tuples. It's clearly a backend bug, because
the duplicates are duplicate right down to the OID. There's no way that
a client could request creation of two tuples with the same OID, right?

I speculate that the backend is updating a tuple (or rearranging a page
to update another one) and neglecting to mark the old copy dead.
I don't know whether having multiple backends running in parallel is
necessary to cause the bug, but it seems likely --- if this kind of
thing happened with only one backend, surely it'd have been fixed long
ago.

The interesting thing is that both tuples are getting inserted into
the table's indexes, because the way we generally find out about it
is that a client fails with "Cannot insert a duplicate key into a unique
index" when it tries to UPDATE one of the duplicated tuples. Since the
UPDATE is "... WHERE id = constant", presumably this indicates that both
tuples are getting found by the index search. (But there are duplicate
tuples, not duplicate index records pointing at the same tuple, because
I see the duplicates if I just dump out the table with COPY. Also,
once or twice I have seen near-duplicates in which the OID is the same
but one or two of the other fields disagree. Possibly these were formed
at the instant of updating the original tuple to modify those fields,
with the original tuple not getting cleared?)

I rooted through the archives and found mention of this sort of thing
from last year sometime, as well as a current thread on pgsql-admin
that looks like it might be related.

Can anyone give me guidance on dealing with this? Any chance that a
fix is already present in 6.4-beta? I'm going to start out by trying
to develop a repeatable test case, but I don't really know enough about
the backend innards to debug it competently...

regards, tom lane