Да, сочетание "коллеги по работе" ошибочно, хотя коллегами называют не только людей, работающих в одной организации, но и людей, имеющих общую профессию, общие профессиональные интересы и т. п.

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

Конечно же, нельзя упрощать язык – например, признавать именами прилагательными только такие слова, которые изменяются по адъективному склонению (бежевый, бордовый). Нет, к разряду имен прилагательных относятся и неизменяемые слова беж, бордо  и многие-многие другие (ажур, аллегри, ампир, апаш, аплике, банту, барокко и т. д.) Это несклоняемые прилагательные с нулевыми флексиями, достаточно подробно они описаны в академической «Русской грамматике» 1980 года.

Вадим, склоняемость / несклоняемость не есть основной признак для классификации частей речи. Главный признак слов, объединяемых в одну часть речи, – наличие обобщенного значения, абстрагированного от лексических и морфологических значений всех слов данного класса. У имен прилагательных такое значение – выражение непроцессуального признака предмета: апельсины цвета (какого?) беж, юбка (какая?) мини и т. п.  Да, большинство прилагательных выражают это значение в словоизменительных морфологических категориях рода, числа и падежа – но далеко не все.

Склоняются. Подробно см. в Письмовнике.

Постараемся ответить подробнее. Варианты завкафедрой, замдекана, завбиблиотекой орфографически правильны. Первые части сложных слов зав..., зам... пишутся слитно. Однако такие формы более характерны для устной речи и не всегда могут быть уместны на письме (например, вряд ли возможно в подписи к официальному документу: завбиблиотекой). Полные же варианты заведующий библиотекой, заместитель декана являются стилистически нейтральными и применяются как в устной, так и в письменной речи. От них и образуются сокращения зав. библиотекой, зам. декана, являющиеся нормативными и общеупотребительными.

Девушка права. Мягкий знак не пишется после шипящих в подобных звательных формах мужских и женских имен. Правильно: Миш, Наташ, Настюш, Ванюш, Катюш  и т. п.

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

Как правило, употребляется с местоимением.

Согласно «Большому толковому словарю русского языка» под редакцией С. А. Кузнецова, клиент – 1) лицо или учреждение, пользующиеся услугами адвоката, нотариуса, банка и т. п. (Клиенты сберкассы); 2) постоянный покупатель, заказчик, посетитель (Клиент всегда прав).

Общее правило таково: служебные слова, входящие в состав западноевропейских фамилий, пишутся со строчной буквы (ван, де, делла и т. п.). Однако есть исключения: Ван Гог, Ван Дамм.