ИМХО незаконно. Особенно если там стоит действительно "verboten". У меня написано только, что я обязана оповестить работодателя

в случае если у меня появится Nebenjob. (как будто мне 40 часов в неделю мало). Ну и в некоторых профессиях могут запретить работать

на непосредственных конкурентов не только как Nebenjob, но ещё и три года после увольнения. Надеюсь, это не Ваш случай.

Право на свободный выбор работы узаконено конституцией вообще-то.. Трудно заставить человека работать, если он не хочет,

но запретить работать, если человек сам желает, никто не имеет права.
Вот почитайте здесь:
http://www.akademie.de/wissen/nebentaetigkeit-...

Ein generelles Verbot einer Nebentätigkeit ohne näheren Zusammenhang mit der (Haupt-)Arbeit ist aber keinesfalls möglich.

То есть если подписали договор, шеф всё-равно может уволить, если узнает, что работаете ещё где-то.
Потом уже можно идти в суд, доказывать и даже может быть выиграть, но рабочее место уже будет потеряно.
Если не очень дорожите этой работой, можете брать вторую, но не удивляться потом, что могут быть проблемы.