Каким образом Windows находит перемещенные папки("Папка была перемещена или удалена")
 

Если создать папку с файлами(например с exe'шником) и ярлык к этому exe'шнику и после переместить папку в новое местоположение, то при попытке запуска с помощью ярлыка этого файла выйдет сообщение
"Папка была перемещена или удалена", после которого файл будет успешно запущен , а параметры ярлыка изменены на новую локацию.
Если же создавать ярлык на папку и перемещать ее, то даже сообщения не будет при попытке ее открытия с ярлыка - все успешно откроется.

Интересует - логика , по которой Windows определяет , где находится новое местоположение перемещенного файла/папки .

Чудес не бывает, этот "механизм" нередко ошибается. Вам пока попросту везло ;)
похоже, просто поиск по имени

Так и хотеось бы понять, - как это делает Windows ?
Чудеса и везение здесь не при чем - это работает ВСЕГДА! Что у меня , что у Вас . Хотеось бы разобраться - что происходит при этом.

kefi, можно здесь почитать:
Distributed Link Tracking and Object Identifiers