I reproduced the following deadlocks on PS 5.5.24 and community v5.6.19. They look the same as the one in the original reporting and could theoretically happen in the trigger situation with pt-osc: 1) deadlocks happened on two different rows,(in the pt-osc case, two UPDATEs on different rows in the base table, they proceeded, but the triggered REPLACE statements got into deadlock).  2) the record locks held and waiting are all on unique key locks. 

I tried it on community version because the deadlock section would give more information on the particular record lock. As below, the “heap no” is the same which means the index record was the same even though the rows to be updated were different. This suggested that the lock was on a non-leave record, to my understanding. It certainly looked interesting that Transaction2 held X lock not gap and requested X lock again. Maybe between the DELETEs and INSERTs of the concurrent REPLACE statements, the shared non-leave record later needed X gap lock?

Here is the deadlock from PS 5.5.24
------------------------
LATEST DETECTED DEADLOCK
------------------------
140624  7:10:30
*** (1) TRANSACTION:
TRANSACTION D6B79, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 5 lock struct(s), heap size 1248, 4 row lock(s), undo log entries 2
MySQL thread id 496045, OS thread handle 0x7fbe1c9ae700, query id 1605727 localhost 127.0.0.1 msandbox update
replace into test1 (id,uid) values('3d294b45fb5611e3889f001e67998d81','3d294b45fb5611e3889f001e67998d81')
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 22 page no 1733 n bits 184 index `uk` of table `test`.`test1` trx id D6B79 lock_mode X waiting
*** (2) TRANSACTION:
TRANSACTION D6B78, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
4 lock struct(s), heap size 1248, 3 row lock(s), undo log entries 2
MySQL thread id 496044, OS thread handle 0x7fbe1958a700, query id 1605726 localhost 127.0.0.1 msandbox update
replace into test1 (id,uid) values('3d29f881fb5511e3889f001e67998d81','3d29f881fb5511e3889f001e67998d81')
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 22 page no 1733 n bits 184 index `uk` of table `test`.`test1` trx id D6B78 lock_mode X locks rec but not gap
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 22 page no 1733 n bits 184 index `uk` of table `test`.`test1` trx id D6B78 lock_mode X waiting
*** WE ROLL BACK TRANSACTION (2)


Here is the deadlock from community version 5.6.19 with more lock details:
------------------------
LATEST DETECTED DEADLOCK
------------------------
2014-06-20 01:06:38 7f488c064700
*** (1) TRANSACTION:
TRANSACTION 383294, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 5 lock struct(s), heap size 1184, 4 row lock(s), undo log entries 2
MySQL thread id 182941, OS thread handle 0x7f485fa02700, query id 558909 localhost 127.0.0.1 root update
replace into test1 (id,uid) values('30fdc71df7bc11e39110080027303a4b','30fdc71df7bc11e39110080027303a4b')
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 112 page no 23 n bits 296 index `uk` of table `test`.`test1` trx id 383294 lock_mode X waiting
Record lock, heap no 76 PHYSICAL RECORD: n_fields 2; compact format; info bits 32
 0: len 30; hex 333066666137646366376263313165333931313030383030323733303361; asc 30ffa7dcf7bc11e39110080027303a; (total 32 bytes);
 1: len 30; hex 333066666137646366376263313165333931313030383030323733303361; asc 30ffa7dcf7bc11e39110080027303a; (total 32 bytes);

*** (2) TRANSACTION:
TRANSACTION 383295, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
4 lock struct(s), heap size 1184, 3 row lock(s), undo log entries 2
MySQL thread id 182942, OS thread handle 0x7f488c064700, query id 558910 localhost 127.0.0.1 root update
replace into test1 (id,uid) values('30ffa7dcf7bc11e39110080027303a4b','30ffa7dcf7bc11e39110080027303a4b')
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 112 page no 23 n bits 296 index `uk` of table `test`.`test1` trx id 383295 lock_mode X locks rec but not gap
Record lock, heap no 76 PHYSICAL RECORD: n_fields 2; compact format; info bits 32
 0: len 30; hex 333066666137646366376263313165333931313030383030323733303361; asc 30ffa7dcf7bc11e39110080027303a; (total 32 bytes);
 1: len 30; hex 333066666137646366376263313165333931313030383030323733303361; asc 30ffa7dcf7bc11e39110080027303a; (total 32 bytes);

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 112 page no 23 n bits 296 index `uk` of table `test`.`test1` trx id 383295 lock_mode X waiting
Record lock, heap no 76 PHYSICAL RECORD: n_fields 2; compact format; info bits 32
 0: len 30; hex 333066666137646366376263313165333931313030383030323733303361; asc 30ffa7dcf7bc11e39110080027303a; (total 32 bytes);