The only way they can do this (legally) without presenting a warrant involves a "National Security Letter", but even those need to go up before a secret court.
Another win for redundancy in your hosting! Especially across jurisdictional boundaries. Hopefully the affected customers and service provider will be able to recover damages from business continuity insurance.
(Shooting it out with federal agents who have arrived to perform and illegal search/seizure is a bad idea...)