The really irritating thing about voicemail is that unlike email, there's no random access to voicemail messages. Unfortunately this is really because it's being presented to you in audio, which is a fundamentally linear medium.

(Audio menus are a not very successful attempt to get around this.)

This means that the real solution is to have your voicemail emailed to you, or put up on a website, or in some other way available through your computer, where you can use all sorts of good random access technology on it. Ideally you would have your phone hooked into this system, so you could use the phone for playback and the computer for control.

(Many years ago I saw a Northern Telecom prototype office thing that integrated a computer with a phone in much this manner, courtesy of knowing someone who worked there. Even back then it was stunningly compelling, although presumably something sunk it since I've never heard of it since then.)

With Asterisk on the right hardware and some work, you could presumably build this today for free. Using VoIP phones would make it even easier, since they're closer to merging computer audio and conventional phone audio.

(I like phones for this because they are a good way of avoiding the speakerphone effect you would otherwise get from people using computer speakers to listen to their voicemail. While you could get the same effect by persuading people to use headphones instead, plugging in and putting on headphones is a lot more hassle (and thus more likely to be skipped) than just picking up the phone.)