I already played with the safes example and broke it. There I assumed a certain dependence among the safes, where the small safes each holds part of the function, and opening 100 small safes is equivalent to opening the single large safe.
I also noted the waiting time will be considerably shorter. Opening one safe at a time, guessing one more bit with each safe, is a Negative Binomial distribution with an expected value of 200 (at p=0.5).
The thief can do a lot better, approaching O[log(100)], by trying all the safes at once and guessing the bits he has not already learned. As I interpret the problem, the thief has a reasonable chance of guessing the next several bits; 50% chance to guess 1 bit and open 1 safe, 25% chance to open 2 safes, 12.5% to open 3, etc. The number of safes opened on each cycle this way follows a Geometric Distribution until the thief starts running out of safes.