We should also look a bit further afield. Thinking back to an exploratory pilot of Microsoft OCS and the phone system at work:

• time based diversion of phone calls to answering machine/other phone
• ability to have the voicemails made into emails and sent to an account. This only works well if your email system then allows you to edit/comment on the email so you can do the voice->text conversion yourself
• Following on to the above, also send the contents of the voicemail to a website. This allows you to check voicemail if you don't have your phone, and also to make a website with comment that could address the "I want to store a text translation" idea just above.
• When changes are made the website, email them so that they could be easiliy accessed offline on the N900.

Yes, some of those clearly require a server providing services. But if the hooks are designed in, it's easier to make the service.

Also, take a look at the Visual Voicemail service on the iPhone. I think it provides off-phone access to the voicemails, which is a very important function in my book.