National key storage
How about this for a compromise: when two endpoints A & B negotiate a shared encryption key, make them use 3-way negotiation, between A, B and K where K is a national key storage facility which stores keys for a limited time and releases keys to security services following a suitable legal process.
By "3-way negotiation" I'm presuming it's possible to securely generate a key known by 3 parties but not by eavesdroppers.
I'm not advocating a facility to record the data (encrypted or unencrypted), just to record decryption keys (for a limited time) for cases when the security services already have wiretapped data for which decryption is likely to be in the national interest.
This is a compromise to privacy, and safeguards would need to be in place such as publishing the number of key requests, but it's better than forcing all encryption to have back doors, which any attacker could use.