It indeed its a rat race, and if you make one real mistake, all other things become worthless. The way this is done is not to everything. The way is to determine in real-time what to store and what not. If that can be done with metadata, you do not even need to decrypt real-time, but if you want, say, keywords, then you have to. That goes into RAM and then what matches goes into more permanent storage. Not that hard to do and do not forget the routers this is usually being done on are expensive enough that this capability does not make that much of a price difference.
As to speed, while not all traffic is monitored, said 17432 hardware AES engines (speed was from an AMD CPU, others may be faster), may cost less than 1 million on pure hardware. The keyword-matching is done in a streaming fashion on FPGAs, BTW. But yes, it will cost more. But even if it is 1 billion, the NSA has that type of budget.