What is the block verification procedure, and will it ever become too expensive?

Question

I'm trying to get a grasp on which items the network is responsible for validating / enforcing. If I understand correctly, when a new block is received, the recipient needs to verify the following:

• the block hash - i.e. that the hash of the header, including prev. block hash, Merkle Root hash, time, target, and nonce is correct, and that its value is less than the target.
• the target - needs to equal the current (difficulty) target.
• the hash of the prev. block - must be correct, and must "point to" the end of the currently "longest" (most difficult) chain.
• all the transactions in the block. This seems like it would involve: looking up the input txn's of the current txn's by their hashes, and running the appropriate sigScript + pubKeyScript pairs. Also verifying for each txn that sum(inputs) >= sum(outputs).
• the coinbase transaction. sum(outputs) >= the "change" left by all the other current txn's.
• hash of the Merkle Root.

Questions:

1. Have I missed anything? (timestamp?)
2. This seems like a lot of work! Particularly scanning through the entire blockchain to find the input transactions. (Though I suppose the client could build an index once on start-up.) My understanding is that at least #4 is optional - a node could choose to assume that it's been done by somebody else. As the blockchain grows larger & larger, wouldn't it become less feasible for individual nodes to do all this work every 10min, resulting in fewer verifications being done?
3. Does a node have to verify every block (and thus every txn) when it first downloads the chain? It's one thing to verify all the block hashes, but a new node without any history wouldn't know if the contents were valid - only that X amount of work had gone into solving the blocks.

Answer 1

I) See https://en.bitcoin.it/wiki/Protocol_rules#.22block.22_messages for the full list of checks that must be done on a new block.

II) Only an index of "unspent transaction outputs" need to be kept to check new transactions / blocks, and that index is a few hundred megabytes currently and very comfortably fits in memory. It will get bigger as more people hold bitcoins, but it will not grow without bound and we've implemented incentives to encourage software to make the UTXO set smaller instead of bigger.

III) Verifying every transaction in every old block isn't necessary, and the reference implementation skips the expensive (ECDSA signature) transaction checks up to a compiled-in checkpoint.