I love the Exchange UM system my voicemail is supplied by, though it can take a while to navigate using voice commands if all you want to do is set your voicemail greeting. I (like a lot of people in Microsoft UK) set the greeting every day to set expectations of what I'm doing, and when I'm likely to pick up voicemail.
Using this dial string, create a new contact on your phone and set it with a speed dial (obviously, I use a Windows Mobile device, but the same concept should be possible on any mobile):
eg. +44 1234 567890 p2468p0123456#006212
This takes you straight to the "record your greeting after the tone" prompt, and after your greeting is recorded, press the # key and it plays back to you. If you don't want to listen to the greeting but just accept it, press "1" or "2" if you messed it up and want to re-record.