because the voicemail interception technique hadn't been perfected yet?
You do realise the "interception technique" of which you speak is ringing the voicemail number and guessing the PIN. Hardly a complicated process.
I don't doubt the NOTW might have given Payne a phone to be able to listen to the voicemails, after all she was a major investment for the company. She was an unknown quantity and it would be a lack of due diligence if they did not want to know if she was talking to another paper.