If they hang up after deleting it, it's certanly gone.
However if they delete it, realise thier mistake before hanging up they can press 1 which should take them back to "Review Messages", then 3 to "Locate Messages" then 2 for ""Messages Received" then option 1, 2 or 3 in "Source" to retreve it again.
lever.