Bueno, imagino que se podrán recuperar, pero no es algo fácil...
Tendrían que sacar el chip de almacenamiento del teléfono, leerlo con un lector adecuado, y luego recuperar los trocitos... No lo veo yo muy fácil, la verdad. Que me digas de la SD tira, pero... ¿de la memoria interna? No está al alcance del usuario típico de la calle (que además, se la van a sudar tus documentos anteriores

).
Por otro lado, un formateo, y luego instala juegos gordos de la store, hasta llenar la memoria, quítalos, reinstala en otro órden, y así unas cuantas veces, y yo creo que ya será prácticamente imposible recuperar nada.
Eso, si no existe alguna app que haga el trabajo. Pero haciendo esto... yo creo que ya valdría.
Un saludo.