Я вот теперь не знаю что ему делать, предложил уволиться и пожит в России и отсюда поставить Антраг.

Это бессмысленно. Он уже поставил на себе "клеймо" (покинул Aussiedlungsgebiet с целью смены места жительства, работа подтверждает это "невременный" факт).

Неужели они меньше немцы чем те, кто в России или СНГ сидят?

Они не меньше немцы. Но они пошли в обход закона (в понимании ведомства надо было сидеть на попе ровно дома, а не ломиться всеми путями в Германию).

Вам выше Лена предложила, пишите петицию, только без этих смешных "немецкий язык для меня - песня, услаждающая мой изысканный слух" и "все боялись разговаривать на немецком языке, учили его в школе, но мне всё равно была привита немецкая культура", а как-нибудь посерьёзнее, чтобы было воспринято адекватно, а не как шутки-прибаутки. Возможно, если "там" получат одно такое письмо, другое, третье, то когда-нибудь дело и сдвинется с мёртвой точки.