As senhas podem ser armazenadas usando hashes que não armazenam a senha, mas um número que representa a senha. O hash normalmente não pode ser retornado para a senha, portanto, há muito pouca chance de que um comprometimento de segurança represente qualquer senha original. Por exemplo, um simples hash pode atribuir A = 1 B = 2 C = 3, etc ... e, em seguida, somar todos os valores das letras correspondentes na senha. Se você usou essa senha antes, o hash sempre corresponderá, mas não há como obter a senha original conhecendo o hash.
Assim, certamente é possível saber se uma senha foi usada anteriormente sem realmente saber qual era a senha. Se um site em particular usa ou não esse método, você não pode ter certeza.
EDIT - note que o exemplo acima é extremamente simples, apenas para transmitir o conceito de um hash. NÃO é assim que você deve calcular um hash no mundo real, não menos do que devido à prevalência de senhas que produziriam o mesmo hash.
EDIT 2 - um link melhor pode ser link , que descreve hashes no contexto da criptografia. O link anterior para hashes fala sobre eles mais no contexto de agrupamento de dados, para o qual eles também podem ser usados.