A chave exclusiva do Percona MySQL 5.5 está duplicada

Estou totalmente sem ideias, então talvez alguém possa responder à minha pergunta. Temos um servidor MySQL 5.5 da Percona com alto tráfego. A aplicação é em PHP e grava sempre no master. Temos ao mesmo tempo 4 escravos dos quais apenas lemos. Basicamente, é uma configuração mestre-escravo padrão. Na semana passada aconteceu que a replicação foi quebrada em todos os escravos, então verifiquei o que há de errado com o banco de dados. O que descobri é basicamente minha pergunta, como isso pode acontecer: a coluna de chave exclusiva (não a chave primária) de uma das tabelas tem o mesmo valor em 2 linhas. Tentei descobrir se isso aconteceu mais de uma vez, mas não. Aconteceu apenas uma vez, mas eu entenderia por que ou como isso pode acontecer. Para melhor compreensão, aqui estão alguns dados reais de nosso banco de dados:

show create table registeredUsers;
| registeredUsers | CREATE TABLE `registeredUsers` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `userId` varchar(32) NOT NULL,
  `client` varchar(200) NOT NULL,
  `osVersion` varchar(10) NOT NULL,
  `deviceGroup` varchar(50) NOT NULL,
  `registrationDate` datetime NOT NULL,
  `lastAction` datetime NOT NULL,
  `cultureLanguage` varchar(2) NOT NULL,
  `cultureRegion` varchar(2) NOT NULL,
  `cultureCode` varchar(5) NOT NULL DEFAULT 'de-de',
  `lastPush` datetime DEFAULT NULL,
  `pushToken` mediumtext,
  `permaToken` varchar(74) DEFAULT NULL,
  `accessCount` int(11) NOT NULL DEFAULT '0',
  `access` varchar(1) NOT NULL DEFAULT '1',
  `provider` varchar(255) NOT NULL,
  `providerTld` varchar(5) NOT NULL,
  `environment` tinyint(1) DEFAULT '0',
  `udidMd5` varchar(32) NOT NULL,
  `development` tinyint(1) DEFAULT '0',
  PRIMARY KEY (`id`),
  UNIQUE KEY `userId_2` (`userId`),
  UNIQUE KEY `permaAccessToken_2` (`permaToken`),
  KEY `client` (`client`),
  KEY `lastAction` (`lastAction`),
  KEY `deviceGroup` (`deviceGroup`),
  KEY `osVersion` (`osVersion`),
  KEY `cultureCode` (`cultureCode`),
  KEY `udidMd5` (`udidMd5`)
) ENGINE=InnoDB AUTO_INCREMENT=38466378 DEFAULT CHARSET=utf8 |

A coluna problemática é o userId, que é exclusivo. Aqui está uma consulta que mostra que temos 2 linhas com o mesmo valor:

mysql> select userId, count(userId) as ct from registeredUsers group by userId having ct;
+----------------------------------+----+
| userId                           | ct |
+----------------------------------+----+
| 748ec561dbc733452bfd697076787ef9 |  2 |
+----------------------------------+----+
1 row in set (3.53 sec)

Eu nem consigo reproduzir então seria muito legal se alguém tivesse uma explicação para essa situação.

Desde já agradeço, Tamas

ATUALIZAÇÃO Conforme solicitado, aqui está o resultado do agrupamento:

mysql> SHOW FULL COLUMNS FROM registeredUsers;
+------------------+---------------------+-----------------+------+-----+---------+----------------+---------------------------------+---------+
| Field            | Type                | Collation       | Null | Key | Default | Extra          | Privileges                      | Comment |
+------------------+---------------------+-----------------+------+-----+---------+----------------+---------------------------------+---------+
| id               | bigint(20) unsigned | NULL            | NO   | PRI | NULL    | auto_increment | select,insert,update,references |         |
| userId           | varchar(32)         | utf8_general_ci | NO   | UNI | NULL    |                | select,insert,update,references |         |
| client           | varchar(200)        | utf8_general_ci | NO   | MUL | NULL    |                | select,insert,update,references |         |
| osVersion        | varchar(10)         | utf8_general_ci | NO   | MUL | NULL    |                | select,insert,update,references |         |
| deviceGroup      | varchar(50)         | utf8_general_ci | NO   | MUL | NULL    |                | select,insert,update,references |         |
| registrationDate | datetime            | NULL            | NO   |     | NULL    |                | select,insert,update,references |         |
| lastAction       | datetime            | NULL            | NO   | MUL | NULL    |                | select,insert,update,references |         |
| cultureLanguage  | varchar(2)          | utf8_general_ci | NO   |     | NULL    |                | select,insert,update,references |         |
| cultureRegion    | varchar(2)          | utf8_general_ci | NO   |     | NULL    |                | select,insert,update,references |         |
| cultureCode      | varchar(5)          | utf8_general_ci | NO   | MUL | de-de   |                | select,insert,update,references |         |
| lastPush         | datetime            | NULL            | YES  |     | NULL    |                | select,insert,update,references |         |
| pushToken        | mediumtext          | utf8_general_ci | YES  |     | NULL    |                | select,insert,update,references |         |
| permaToken       | varchar(74)         | utf8_general_ci | YES  | UNI | NULL    |                | select,insert,update,references |         |
| accessCount      | int(11)             | NULL            | NO   |     | 0       |                | select,insert,update,references |         |
| access           | varchar(1)          | utf8_general_ci | NO   |     | 1       |                | select,insert,update,references |         |
| provider         | varchar(255)        | utf8_general_ci | NO   |     | NULL    |                | select,insert,update,references |         |
| providerTld      | varchar(5)          | utf8_general_ci | NO   |     | NULL    |                | select,insert,update,references |         |
| environment      | tinyint(1)          | NULL            | YES  |     | 0       |                | select,insert,update,references |         |
| udidMd5          | varchar(32)         | utf8_general_ci | NO   | MUL | NULL    |                | select,insert,update,references |         |
| development      | tinyint(1)          | NULL            | YES  |     | 0       |                | select,insert,update,references |         |
+------------------+---------------------+-----------------+------+-----+---------+----------------+---------------------------------+---------+
20 rows in set (0.00 sec)

ATUALIZAÇÃO 2

mysql> SELECT id FROM registeredUsers WHERE userid = '748ec561dbc733452bfd697076787ef9' ORDER BY id DESC ;
+----------+
| id       |
+----------+
| 38245456 |
+----------+
1 row in set (0.00 sec)

mysql> select userId from registeredUsers where id in (38245456, 38245457);
+----------------------------------+
| userId                           |
+----------------------------------+
| 748ec561dbc733452bfd697076787ef9 |
| 748ec561dbc733452bfd697076787ef9 |
+----------------------------------+
2 rows in set (0.00 sec)

mysql> select id, userId from registeredUsers where id in (38245456, 38245457);
+----------+----------------------------------+
| id       | userId                           |
+----------+----------------------------------+
| 38245456 | 748ec561dbc733452bfd697076787ef9 |
| 38245457 | 748ec561dbc733452bfd697076787ef9 |
+----------+----------------------------------+
2 rows in set (0.00 sec)

mysql> select id, userId from registeredUsers where userId = '748ec561dbc733452bfd697076787ef9';
+----------+----------------------------------+
| id       | userId                           |
+----------+----------------------------------+
| 38245456 | 748ec561dbc733452bfd697076787ef9 |
+----------+----------------------------------+
1 row in set (0.00 sec)

ATUALIZAÇÃO 3 Para ter certeza de que as duas strings são idênticas, aqui está uma consulta que retorna todas as 2 linhas. (Obrigado a sugestão para isso)

SELECT id FROM registeredUsers WHERE userid >= '748ec561dbc733452bfd697076787ef9' LIMIT 2;
+----------+
| id       |
+----------+
| 38245456 |
| 38245457 |
+----------+
2 rows in set (0.00 sec)