Thanks for your analysis Hepatizon! It was about what I was expecting.
However, I don't think this is quite correct.
For one thing, the way the blocks are currently set up, it takes linear time with respect to the total number of transactions (and I think more than that in memory) to verify one transaction. So after 10 years of bitcoin, you need to either go through all 10 years worth of transactions, or have a snapshot of all the account balances of every user ever and work from there.
It appears that each new transaction has direct links to each prior transaction being used as an input. To validate a transaction you only need to validate the immediate dependancies. You don't need to validate those dependancies' dependancies as they were previously validated as part of the block chain. That means closer to constant time rather than linear.
You're right - I keep forgetting that the actual coins are tracked rather that just the account balance. So yeah, you only need to go back find whoever last owned the coins in question and verify that they're the same person sending them. Which is
technically linear time in that if the first coin ever was hoarded for ten years you really would need to go through the entire ten year block chain (unless you indexed it, which would be easy as all the coins are numbered) to see who had it - but in practice it would be closer to constant time because most people won't hoard bitcoins. (Unless they figure out that deflation is all but guaranteed...) For some reason I keep thinking that you would need to verify the account balance of the sender, and that would require verifying the account balance of everyone who has sent the sender money, and everyone who sent them money, and so forth.