4) my script finds the key every time? So far, yes.
Ok, when I ran your original script, it was less than 20% of the time the key was found.
Keep working on the database size. I know you will get it down!
If you can get it down to 1 bit per key like the OPs, then you're onto something. His DB is unmatched so far.
Less than 20%? Did you have try with the last version? Maybe the first version was not correct, I fixed some stuff.