In the UK voicemail is automatically included from your network and usually can't be turned off, though you can record your own message these days.

So any other option is a bit of a nonstarter. Calls to voicemail are either free or part of your 'included minutes' if you're on a plan. I really need n900 to know if someone has left voicemail.