Verifique outras tabelas
É possível que a funcionalidade em questão grave dados em outra(s) tabela(s) e haja algum registro. O sistema, vendo que algo já existe, não grava o usuário.
Erro "mascarado"
Outra possibilidade é estar ocorrendo um erro, mas o seu teste não está pegando isso.
Seria interessante olhar cuidadosamente o log de retorno de cada requisição.
Cache do sistema
Se o sistema possui algum tipo de cache, pode ser que ele tenha uma versão do usuário em memória e pense que ele já existe.
Esse cenário é bem estranho, mas pode ocorrer dependendo de como o sistema gerencia suas entidades. Uma lógica incorreta usando a API JPA do Java pode levar a esse tipo de problema.
Confusão de ambiente
Também ocorre algumas vezes de olharmos a base de dados ou tabela incorreta.
Na dúvida, verifique com o responsável pelo ambiente se houve alguma alteração. Pode ser que alguém tenha configurado o sistema para usar outra instância do servidor de banco de dados.
Registro "perdido"
Outra possibilidade é que o usuário tenha sido gravado durante o segundo teste, mas você não o encontrou porque o ID ou algum campo usado no critério de consulta mudou.
Isso é comum de ocorrer se houver campos gerados automaticamente pelo sistema.
Considerações finais
Tentei enumerar acima os problemas mais comuns que ocorrem em cenários onde parece não haver uma explicação razoável
Entretanto, o problema pode estar tanto no equívoco mais básico, como olhar o banco errado, como nos detalhes mais "obscuros" da arquitetura do sistema.
Se nada disso lhe ajudar, resta fazer um trabalho em conjunto com o desenvolvedor do sistema, que pode depurar o comportamento exato do programa. Lembrando que em situações assim é imprescindível detalhar bem o procedimento para reprodução do problema.