Куда девается файл, удалённый из устройства?

На самом деле никуда.

Удаление файла с носителя - это совсем не то же самое, что стереть мел с доски или краску со стены. Это скорее "вычеркнуть строчку в оглавлении". Вот представляете себе книжку, в которой много глав, и с оглавлением? Система считает, что файл существует, если на него есть ссылка в "оглавлении". Соответственно "стереть файл" - это убрать из оглавление ссылку на него (если совсем точно - то даже и ссылка не убирается, она просто помечается как "удалённая"). Сама информация при этом не уничтожается - просто система начинает считать, что её больше нет и что это место свободно, на него можно записать другую информацию. Именно на этом принципе работают все программы восстановления файлов: они убирают со ссылки на файл метку "удалённая" - при условии, что на то место, где лежит файл, не была записана новая информация.