As above, you know the slebs number so someone in the office calls them and keeps them on the phone, trying to get an interview or something.
Meanwhile, you give them a call on the same number. It obviously* goes to voicemail. When you get “hi, you’re through to Prince Phillip, I can’t get to the phone right now…” you press *. Then it asks you to enter your PIN. No one knew about this service so no one knew to change the PIN. So you press 111 or whatever the default PIN is on your keypad then listen to/record all of the voicemails.
*’Call waiting’ means that this won’t necessarily work now, but I suppose if they switched calls to answer you you’d just say “Hi, I’m from the Sun calling about an interview….My colleague’s already speaking to you? My mistake” and not arouse any suspiscion.