If the police has a warrant, they can present it to your phone provider who are then required to send the data they have about you and your phone calls. This data may include the actual recorded conversations if allowed by the warrant.

This is regulated in the Telekommunikations-Überwachungsverordnung (TKÜV).

Edit: nvm, I didn't see this was about the GDR.

> phone taps are illegal in Germany?

They’re quoting the East German constitution. I think there is a /s missing at the end.