The addresses would be created and stored in the normal place, but also listed on a separate list of created-but-never-used addresses. When an address is requested, the address at the front of the never-used queue is handed out, and a new address is created and added to the back.
There's some kind of rescan in the block loading code that was made to repair the case where someone copied their wallet.dat. I would need to check that the rescan handles the case of rediscovering received payments in blocks that were already received, but are forgotten because the wallet was restored.