Though I can see how that would be convenient for the user, it wouldn't really make sense to have a message only partly deleted from the host company's perspective - does this mean they would need to save all the deleted messages?

Of course, they could provide a window of time, say 60 seconds, during which a message coule be retrieved, so that if the deletion really was just the result of a twitchy finger, it could quickly be brought back.

T-Mobile in the US provides that functionality already ("Press #2? to undelete"), but messages are deleted once you exit your mailbox.