"Pandora's Box" indeed...!
I don't know about the UK, but in the US the rules on recording phone conversations vary from state to state -- some require that all parties be informed and agree to recording, others don't. Anyone using their VOIP-archiving service would have to start every outgoing and incoming call with a "This conversation is being recorded," statement replacing "Hello" as their greeting in order not to fall afoul of the laws here.
Also, if the carriers offered this service, would it have any effect on the wiretap laws? Would the police need to get a wiretap authorization if the suspect has already, essentially, agreed to let his calls be recorded (by choosing to use that carrier)?
I dunno... Sounds more "can of worms" than "Pandora's Box", to me.