They aren't always entirely within their rights to refuse to give up your data: the third party doctrine doesn't transfer your expectation of privacy to the third party holding your data, it says that neither you nor the third party has an expectation of privacy for that information. Subpoenas and court orders and other process short of a warrant can compel disclosure of this "third party" data.
This is why there's a patchwork of statutes requiring Fourth Amendment ish processes for things like wiretaps and emails.
The companies are entirely within their rights to say "fuck off and get a warrant, you ghouls", but from their perspective, it's a lot easier to just hand it over.