Mike@FP just told me about a service Bell Canada run, which lets you dial *directly* into the voicemail of the person you're calling - so their phone doesn't ring and you get to leave them a voice message.
He was talking about it in the context of "this is way better than SMS because it means you can be so much more expressive, without having to actually talk to anyone", but it struck me as a great service - tying into a load of existing infrastructure, and building both voice call and voicemail revenues (which are important to operators) at the same time as providing a new(ish) way of communicating...
Update: Robert tells me that this is, in fact, possible on Orange in the UK - dial your voicemail number, press 2 and you're taken through the process. You can't send messages direct from your address-book though, which is a shame because only freaks remember phone numbers these days.
Walter also comments on this post to say that 3 in Australia (and presumably elsewhere) let you do this.