Hay un programa en android que lo hace pero no me acuerdo de su nombre, voy a revisar el baúl de los recuerdos a ver si lo encuentro
EDITO: Se llamaba Undelete Beta, ahora se llama Undelete for Root Users. Su nombre lo dice todo, si no eres root...
A lo mejor hay otra forma de recuperar los datos en los móviles sin SD pero no la conozco