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 try with the last version? Maybe the first version was not correct, I fixed some stuff.
I don't understand why:
1 bit for 2^32 key is better than 64bits for 2^32/2^20 = 2^12 keys.
Less size, less search time, 100% keys found.
The first version of the script worked, the second does not find matches.
There may be an error in the code.