For me, if I have a new voicemail when openning skype, there will be a red astrick <sp> on the history tab. Going into the history list, click and hold the desired message and you'll get a popup menu with a 'play' option.

My only gripe re skype is that you can't turn off the unnecessary sounds, but leave (incoming call) ringing on.

I use both skype and gizmo, and have call in numbers for both - gizmo ringing thru the new built-in IM client. n800 works great with these services imo.