Нет, супруга-гражданина ЕС (включая ФРГ) у меня нет.

Значит, у Вас и ситуация иная, т.к. на Вас - в отличие от ТС - распространяется тот закон (AufenthG), который действительно содержит обязательство работодателя контролировать наличие у Вас разрешения на работу.

Вопрос даже не в том, по какому закону я здесь пребываю - Aufenthaltsgesetz или Freizügigkeitsgesetz

Вопрос именно в этом.

Zuständig für die Erteilung von Arbeitserlaubnissen bzw. für die Zustimmung zum Aufenthaltstitel ist die Zentrale Auslands- und Fachvermittlung (ZAV) der Bundeagentur für Arbeit mit ihren regionalen Standorten. Sie wird bei der Vergabe des Aufenthaltstitels intern durch die Ausländerbehörde eingeschaltet.

Вы уверены, что это относится к Aufenthaltskarten, выдаваемым на основании FreizügG/EU? Я бы не доверял какому-то сайту, который AufenthG называет Ausländergesetz'ом.

Важно, что если у меня паспорт не ЕС, то я иду в ABH, а уже они запрашивают разрешение на работу у совсем другого ведомства

Не всем обладателям не-ЕС-паспорта необходимо запрашивать разрешение на работу в АВН/службе занятости. В частности, разрешение на работу есть в силу закона у freizügigkeitsberechtigt граждан иных государст ЕС и членов их семьи, проживащих в Германии.

Им пофиг, кто кому жена/муж.

Не всё так однозначно, как Вы это себе представляете (см. выше).

У них на иностранца должно быть разрешение на работу

Верно, при этом у некоторых иностранцев оно уже есть в силу закона (см. выше), поэтому АВН, служба занятости и их решения тут ни при чём.