Depois de excluí-los da Lixeira, eles desaparecem (mais ou menos) do seu sistema. Você precisará usar uma ferramenta de recuperação de arquivos. Eu pessoalmente uso Recuva , que me serviu bem, mas há muito por onde escolher. Se você estiver usando o Mac, não posso recomendar ferramentas, pois não tenho conhecimento suficiente do sistema aqui.
Posso notar também que, se você tiver arquivos na Lixeira, eles serão excluídos após um determinado período de tempo, por isso sugiro que você não coloque arquivos lá que realmente deseja manter.
Para o Linux, usei PhotoRec , mas isso também funciona para Windows e Mac.