What is the block verification procedure, and will it ever become too expensive?
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.