É mais provável que eles verifiquem a senha em relação a tabelas de arco-íris conhecidas publicamente. Se a senha aparecer em uma delas, elas não permitirão que você a use.
Da Wikipedia:
A rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a plaintext password up to a certain length consisting of a limited set of characters. It is a practical example of a space/time trade-off, using less computer processing time and more storage than a brute-force attack which calculates a hash on every attempt, but more processing time and less storage than a simple lookup table with one entry per hash. Use of a key derivation function that employs a salt makes this attack unfeasible.
Em suma, uma tabela de arco-íris é um banco de dados de senhas comuns e incomuns, convertidas em vários hashes. Por ter o resultado final de um hash de senha, você não precisa usar força bruta para hacká-lo.
É provável que sua senha, por mais aleatória que você ache possível, esteja em uma das tabelas de arco-íris conhecidas. Verifique este site para ver as tabelas reais do arco-íris.