At a fundamental technological level you are increasing the size of available memory by using the memory of other nodes. And there are ways you can query other nodes about their subset of unspent transactions by using a merkle tree. If you trust the root of a balanced merkle tree you only need O(log(n)) computations [2] to prove that a leaf belongs to it.
This sharding mechanism could be added to bitcoin where the root of the merkle tree of the unspent transactions is added to each block. Nodes on the network can store a sub-tree of arbitary size and validate part of each block. Whether this scheme would be robust to dishonest miners is still an open question though.
[1] http://gavinandresen.ninja/utxo-uhoh [2] https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee...