Here on Vodafone pay-as-you-go, voicemail minutes appear to cost the same as calls, that is 20p/minute... I have a Three USIM ready with much better terms, the Vodafone PAYG is just a cheap thing to keep me going until I have an N900 to put the USIM into :-) (Hope they fix the "not compatible with Three USIMs bug soon!)