Andrew,

I think a much better question I now have. What are the steps involved in verifying the block chain?

1. Verify each transaction (highly parallelizable? )
2. Verify each block hash.. ~300k hashes, could be done in serial
3. ... ?

So a big issue you have encountered is that transactions many blocks away from each other that reference each other mean a breakdown in the parallelizability? (that is an awesome word) Because if you wish to verify a single block you might have to look far up or down the chain to find if that specific address really does have x btc to send to another address in the current block?