That's the subtle part: they aren't two versions of the same record. They're two entirely different records, so all bets are off. (In your example, they don't even have the same primary key because no primary key is declared. PostgresSQL doesn't know that k is supposed to be a key; it's just another column.)
That is an implementation problem. The behavior is still incorrect. MySQL manages to do this correctly, so it's clearly not impossible. I can't come up with any other conclusion except that transaction isolation in pg is fundamentally broken when I see this type of case show up.
