If you have 1 MB block size limit and each input is approximately 250 bytes, you only have at most 4000 inputs per block.
Well, the size limit (at least the 1MB version) is not likely to last indefinitely.
The block chain would have to be saved with a flag to indicate if the output was consumed. This flag could be set when the tx is burred enough that a reversal is unlikely.
However, it does reduce the overall performance of the system.
As for inputs in transactions not included in blocks, you can just drop ones you cannot fetch in a reasonable time. There is nothing wrong with dropping transactions.
That is part of what I meant. If a tx message could have meta-data attached, then at least you could prove that the tx output actually exists. This acts as a way to prevent spam.
Keeping only recent UTXO set elements in RAM and the rest on disk would be the end result.
If it is harder to spend "old" transaction outputs, then that weakens the ability of the system to act as a long term store of value.
Bloom filtering could be used. If every node had a different random seed for the hash function, then producing the false positive that propagates would be hard.