1.Программа НЕ была деинсталирована. Программа не была удалена. Была удалена dll. Программа стартует, не находит dll и сообщает о ошибке.
2.
Исключая замороченные варианты с вирами, все, что стартует и не является частью операционной системы есть в списке.
3.
Какие записи вы собираетесь искать в реестре? dll прописывается или в стандартном месте, где все dlls или лежит в каталоге программы. Путь к ней не прописывается в реестре. Сама программа может быть тупо в папке автозагрузке и вообще не иметь регистрации в реестре. Может и быть в разделе автозагрузки реестра, но сам раздел нужно найти и в том списке также разобраться и не снести что то важное.
4
У меня в разделе автозагрузки где то 40 записей, часть которых уже отключена. Многие программы будут автору известны. Возможно он вспомнит, что стирал в последнее время. Можно также отключать половину программ, потом половину от половины - перебрать 40 записей таким образом можно за 5 попыток. Так быстро я не синею