Believe me, I would have addressed that if there was an explanation from the Bitcoin project about how it plans to handle scaling. The documentation is pretty spread out on the wiki, and even after reading the forums, the potential for a scaling problem *seems* to be just another one of the areas in which the system would benefit from a thorough third-party review from domain experts.
I do know that clients relay what amount to transaction-id-hashes to each other to propagate messages, rather than full transaction logs, which is presumably one way they attempt to reduce overhead in the protocol.
The "network" wiki page is a pretty good starting point for digging in to this stuff, but like I said above, the overall picture of how the network works is kinda scattered out.
PS - I guess it's also plausible that users would not regard it as mandatory that the *entire* network validate a transaction before they consider it a done deal; as time goes on you accumulate more and more "confirmation" messages for each transaction you've conducted. But it's technically valid as soon as a block that includes it is solved and becomes part of the block chain.