That has got to be one impossible rainbow table.

More likely they used a table of known existing passwords and variations on the them?