Sí. No importa que los archivos no hayan pasado por la papelera.
La única forma de no poder recuperarlos es que te hayas cargados los archivos con algún programa definitivo como el Eraser, que le hayas hecho algo físico al disco (como pasarle un imán por encima) o que haya pasado mucho tiempo y se haya sobreescribido la información que "eliminaste" en tu disco duro.
Imagino que si formateas pues tampoco podrás a menos que tengas los medios necesarios (es decir, esos que tiene la poli

)
Un saludo