It doesn’t have to be one key for all, one key for a bucket, per user if needs be. Can’t these master keys be in offline HSM’s? I get your argument, but it doesn’t seem an impossible problem to solve.
And put the HSMs where? In a big room? Protected by a door, with one key?
Or maybe each of the 650 elected politicians gets to hold 10 HSMs, each holding 10,000 keys? That way, by distributing trust, we can be completely sure that politicians are always snooping on about 10% of everyone's mails, instead of worrying about whether it's 100% or 0% at any particular moment.