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.
How about a menu of selectable 5 items, [X] Show All Or Show Only: [ ] Incoming calls [ ] Outgoing calls [ ] Missed calls [ ] Voicemail and maybe multiple selection enabled for the last four?