Опять пришло письмо предоставить документы, что его семья была под комендотурой и в труд.армии. Всем известно, что такие документы на руки не выдавались.

Выдались и выдаются репрессированным или их потомкам на руки после 1991 года без проблем. В частности, архивные дела (не всегда), архивные справки и справки о реабилитации. Про нахождение в трудовой армии документальное подтверждение найти будет непросто, т.к. ТА не считалась репрессий и не считается до сих пор, но в военкомате по месту мобилизации или по месту "службы" могут быть сведения.

Вашему отцу должны выдать справку о реабилитации, как ребенку репрессированных родителей. Сам он лично репрессирован не мог быть по национальному признаку, т.к. был несовершеннолетним на момент репрессий (конечная дата 1955 год, Вашему отцу тогда было лет 10, а национальность выбирали только в 16 лет).

Где мне что искать, в каких архивах? Их навепняка уже не существует

Ищите справки о репрессиях на родителей отца, ведь он только в 1945-м году родился и может вести происхождение только от своих родителей. Делайте запросы в ИЦ МВД (справедливо только для РФ) по месту их нахождения под репрессиями или по месту жительства до репрессий, если такие были. Начните с ИЦ МВД по месту рождения Вашего отца.