There is a bug where the creation of the first-ever address (with label "Your Address") does not trigger filling of the keypool. The keypool is only filled once the next address is created, and then it takes tens of minutes to fill completely.
I guess I can confirm this bug, and I demonstrated it in a spectacular fashion.
The sad thing is, I think the 100-address pool is meant to help protect against loss like happened to this guy:
http://forum.bitcoin.org/index.php?topic=782.0
But if this 100-address pseudo protection didn't exist, I would have been obsessively making completely new backups after every transaction. The 100-address pool sort of tricked me into a false sense of security.
I know it's my fault for relying on the pool without verifying that it actually existed. I don't think I've ever been this depressed, I'm actually crying. I can't believe this happened.