I've been using Hullomail for voicemail since 2008. Its free and the best internet service I use, okay maybe apart from GMail.

Once you sign up you set the busy/unreachable divert on your phone to Hullomail's number rather than your voicemail - Hullomail will then take the voicemail from your caller. Basically it will then MP3 the message and email it to you. Works with practically any email service.

The neat stuff is actually the GMail integration. If you have a GMail or Google Apps account, it will link up with your contacts - so say if Tony leaves me a message, it will look up his number in my contacts and send me an email saying that Tony left me a message. It'll have Tony's email address as the reply address, his contact icon as the MP3 album art and all the ID3 information correctly populated. Neat. Works for missed calls too where people get diverted but don't leave a message. Of course, it will label these messages for you.

Other neat features is the visual voicemail application, you can get this for Android, iPhone and BlackBerry too. Works just like iPhone visual voicemail and is linked to the read/unread status of the voicemails in your email inbox.

Plus, it has a standard voicemail number to call (and PIN if you call from a number that is not yours) so you can treat it like a traditional voicemail service if you want to and hear the lady ask you to press a button to hear your voicemails. So the whole service even works perfectly if you don't have a smartphone.

Works in the UK and the US too. Really recommend it.