They’re not outside the law, if the police come knocking with a legal request they have to provide data\details they have. What would you have them do?
In this specific case of a recovery email address, maybe there is something that could be done so that they wouldn't hold the email address itself. At least 2 options come to mind.