deadlock in single-row select-for-update + update scenario? How could it happen?

I have developer with pg 9.3.5, which is reporing something really strange.

He runs importer, which does, in single transaction:

begin;
select * from table where pkey = <value> limit 1 for update;
update table set ... where pkey = <the same_value>;
commit;

and two backends running the same transaction deadlock.

I checked for duplicated rows with the same pkey value - none are there.
And frankly - I'm out of ideas.

What could be wrong in such case?

Detailed logs, with just some obfuscation:
https://depesz.privatepaste.com/0594a93459

depesz