My phone, a Nokia N73, came on an O2 contract but I’ve switched to Orange. Unfortunately that means that when I press the voicemail button the phone dials 901 (O2’s number).
I couldn’t figure out what the Orange voicemail number was which was a bit of a pain. Luckily I found it quickly.
A few minutes googling revealed it to be 123. This seems to work for Pay As You Go and contract customers alike.