Let me start by seeing if I'm guessing on the right track.

It seems to me that the ONLY way you could scale to this degree is with a segragated witness style scheme. VERY VERY roughly it seems like the idea would have to be that each node will only monitor a small fraction of the total network, and any time you are interested in a transaction that is not taking place on the part you are monitoring, you will be forced to trust the consensus of the percentage of the network that IS monitoring the transaction you are interested in.

Am I on the right track?