Some wallet applications that create new private keys randomly keep a pool of unused pre-generated keys (BitcoinQT keeps 100 keys by default). When a new key is needed for change address or a new payment request, the application provides the oldest key from the pool and replaces it with a fresh one. The purpose of the pool is to ensure that recently used keys are always already backed up on external storage. Without a key pool you could create a new key, receive a payment on its address and then have your hard disk died before backing up this key. A key pool guarantees that this key was already backed up several days before being used. Deterministic wallets do not use a key pool because they need to back up a single secret key.