Also, it's nice that you can recover the key to an address if you know the wallet seed, but if you lose the wallet how do you keep track of which addresses you control in the first place? Is it possible to build a list just from the wallet seed?
Yes.
It generates a series of key pairs.
If you had money in address number 20,000, then you would need to compute addresses 1 to 19,999 before you can work out 20,000.
It is reasonably fast. It takes a few ms to generate an address. Dedicated code can do it faster.
If you thought the first 100k addresses were used, you might compute the first million when doing a recovery, so you don't miss any when scanning the blockchain.
The new deterministic wallets have a suggested "gap" length of 20. This is for use by the general public. Merchants could have higher gap lengths.
It computes the first 20 addresses. If it sees address 17 in the block chain, then it computes addresses up to address 37 and so on.
This means that you can have a "gap" of up to 20 unused addresses and it would still find all your addresses.
The client might warn the user if they asked for the 20th address in a row of spaces that it is the last one and it must be used before any more can be computed.
When importing, it might use a gap of 40, in order to be safe.