How do deterministic wallets know how many keys to generate? Say I backup the "seed/key" for a deterministic wallet. I then create 10,000 transactions, resulting in 10,000 new addresses being generated.

Say I then lose the wallet file and I restore from the "seed/key". How does the deterministic wallet know it has to generate 10,000 addresses to get the full balance?
You've hit upon an important issue, and one that there isn't a perfect solution to.

Your thin client (most clients that use deterministic wallets are thin clients, but not all) goes through the following process:


Generate an address.
Look at the blockchain, and see if it has a balance.
Repeat with next address, unless the addresses we've checked have had a balance of zero for a long time.


The number of empty addresses you're willing to check before giving up is called the gap limit.

The gap limit can't be too low, or there's a possibility that someone will backup from a wallet seed and not see all of their money. (If this happens to you, increase the gap limit and try again.) It also can't be too high, or you'll waste resources on the servers handling Electrum queries.

Your suggested scenario is actually the easiest to solve, because if each of those addresses has a transaction associated with it in the blockchain, the client knows that it showed that address to you at some point, and will keep searching.