Because the telecommunications companies are eager to cooperate with the police. Since third-party doctrine applies, the privacy of the company, not the client, is considered, so Verizon happily consents to all police searches of phone records.

This has been discussed all the way up with SCOTUS (dominated by the Federalist Society at the time) so its legal.