That was the main way.

Another was some networks had a voicemail number you could dial into from abroad and then enter the phone number and pin of the voicemail box you wanted to access. Before this scandal nobody has ever changed that pin, or known about it, in the entire history of british telephony.