And no, putting company's in charge of your privacy isn't a solution, if they can be compelled to give away your communication history then they'll abuse it. Have you not learned anything from the Snowden leaks?
And it's not true that with electronic communication you either get full privacy or none. You can have end-to-end encrypted messages with unencrypted metadata, so that when police observe a message implicating the sender in a crime (e.g. on an arrested suspect's phone) they can get a search warrant for the IP address or phone number associated with that account and then visit the owner in person to look at the messages on their phone. This doesn't allow police to read everyone's messages all the time undetected, but does allow them to read specific people's messages if they get a warrant.
Since Telegram doesn't only have unencrypted metadata but also plenty of unencrypted messages, there must've been many cases where a search warrant would've yielded lots of useful information. If Telegram didn't properly respond to all warrants, it seems fair to launch an investigation.
With such a setup what does it mean to comply with warrants? Are we saying that Telegram should voluntarily yield all information regardless of jurisdiction?
and they're usually public property and policed. Routine police inspection on a road and in particular control of borders and key nodes in your transportation infrastructure isn't exactly controversial. (unless you're part of some extreme political faction). You know a lot of countries where people can drive without a license plate?
Private communication is important but it has always had limits, this crypto mentality of companies exercising no compliance, having no borders, ignoring the law and national security doesn't have a precedent. Historically people communicated say in the US using an American telecommunications network which without a doubt complied with legal requests. It's not at all self evident that we should tolerate telecoms infrastructure operated by a Russian out of Dubai that is primarily used by an enemy we're effectively at war with.