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

В полном академическом справочнике «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина о подобных случаях говорится: 

«§ 73. Обороты со словами смотря по, начиная с, потерявшими свое глагольное значение и перешедшими в предлоги и предложные сочетания, не обособляются: Будем действовать смотря по обстоятельствам (ср.: по обстоятельствам); Начиная со вторника погода резко изменилась (ср.: Со вторника погода резко изменилась). Если же эти обороты имеют значение уточнения или присоединения, то они обособляются: Будем действовать умело и быстро, смотря по обстоятельствам; На прошлой неделе, начиная со вторника, погода резко изменилась».

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

Ваши коллеги не вполне правы. Глагол пойти в конструкции пойду и (сделаю что-либо) имеет значение "приступить к действию, обозначенному вторым глаголом". Такие конструкции широко распространены в разговорной речи. Например: Вот пойду и мультики смотреть буду! А идти никуда не могу — тетя Диана так за меня боится… [Леонид Каганов. Танкетка (2011)]; И грозил со слезою в голосе: — Вот пойду и застрелюсь [В. Г. Галактионова. Спящие от печали (2010)]; Однажды на репетиции Завадский... вскочил и с криком «Пойду и повешусь!» выбежал из зрительного зала [Алексей Щеглов. Фаина Раневская: вся жизнь (2003)]. Очевидно, Ваши коллеги решили, что в произнесенной Вами фразе соседствуют два глагола движения (пойти и поехать), отчего она и действительно выглядит неловкой. Однако подчеркнем, что грамматически такая конструкция вполне закономерна. 

Вот что говорится о подобных случаях в параграфе 15 справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина:

Тире между подлежащим и именным сказуемым не ставится: <...>
Если сказуемое выражено оборотом со сравнительными частицами как, словно, что, точно, вроде как и др.: Жизнь как легенда; Небо словно раскинутый шатер; Брошка вроде как пчелка (Ч.); Лес точно сказка; Неделя что один день. Быстро проходит; Пруд как блестящая сталь (Фет). <...>
Примечание
При акцентировании сказуемого (обычно в стилистических целях) тире возможно: Этот одинокий и, может быть, совершенно случайный выстрел — словно сигнал (Фурм.); Во рту у него горько от табаку-самосаду, голова — как гиря (Шол.); Чернеющие прогалины — как черные острова в белом снежном море (Бун.); Млечный Путь — как большое общество (Б. Паст.); Луна в небе — как среднеазиатская дыня (Ток.).

Опираясь на многочисленные примеры из художественных текстов, можно утверждать, что в конструкциях, начинающихся частицей «только и» и содержащих союз «что», перед союзом последовательно ставится запятая. Да, в справочнике Д. Э. Розенталя «Пунктуация» указано: запятая не ставится перед союзом что в выражении только и… что, за которым следует существительное или местоимение: Только и денег что пятак в кармане; Только и всего что рубашка на теле; Только и развлечений что кино раз в неделю; Только и свету что в окошке; Только и разговоров что о них двоих. Однако примеры из художественной литературы опровергают эту рекомендацию, они свидетельствуют о том, что и в этих случаях перед союзом ставится запятая: Только и света, что внучки! А кто их знает, какие они будут? И. Гончаров, Обрыв. За многочисленными столиками гул стоял, только и разговоров, что о последних событиях в столице. В. Шишков, Емельян Пугачев. Так что запятую в подобных конструкциях предпочтительно ставить.

Вводное слово например выделяется запятыми: Припоминается, например, что вот здесь ровно год тому назад, ровно в это же время, в этот же час, по этому же тротуару бродил так же одиноко, так же уныло, как и теперь! Ф. Достоевский, Белые ночи.

Если вводное слово стоит в начале обособленного оборота, запятые ставятся перед вводным словом и после всего обособленного оборота. После вводного слова запятая не ставится (иначе говоря, запятая, которая должна была «закрывать» вводное слово, переносится в конец обособленного оборота): ...Относительно золота, которое добывал Калиостро без всяких трудов из всех других металлов, например из меди, прикосновением рук превращая их в золото, Строганов тоже был невысокого мнения. Ю. Тынянов, Гражданин Очер.

Если оборот заключен в скобки, то стоящее в его начале или конце вводное слово отделяется запятой по общему правилу: На праздники мы решили куда-нибудь съездить (например, в Ригу).

«Объяснительный русский орфографический словарь-справочник» (Ин-т русского языка им. В. В. Виноградова РАН; Е. В. Бешенкова и др. М., 2015) сообщает о сочетании (в)глубь следующее:

вглубь 1) пишется слитно как наречие от существительного (глубь), принадлежащего к закрытому ряду слов с простран­ственным или временным значением (распростра­ниться вглубь и вширь, проблему не решили, а загнали вглубь); 2) закрепившееся слитное написа­ние предлога (зверь забился вглубь норы).

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

Правило таково: дефис не пишется, если предшествующее однословное приложение может быть приравнено по значению к определению прилагательному: красавица дочь (= красивая дочь), старик отец (= старый отец). Напрашивается ответ, что дефис не нужен: старики полковники (= старые полковники). Однако в названии фильма «Старики?полковники» содержится явная аллюзия на известный фильм Эльдара Рязанова «Старики-разбойники» (1971), в названии которого дефис пишется, и это объяснимо: смысл сочетания не 'старые разбойники', а 'старики, ставшие разбойниками' (по сюжету фильма Рязанова два друга-пенсионера решили организовать «преступление века», чтобы один из них, следователь, смог избежать увольнения, раскрыв это преступление). Очевидно, по аналогии с названием «Старики-разбойники» дефис пишется и в названии «Старики-полковники».

Кроме того, отметим, что в недавно вышедшем из печати полном академическом справочнике «Правила русской орфографии и пунктуации» сочетания типа старик-отец предлается писать через дефис (что вполне логично и снимает все вопросы). Подробнее об этом см. в ответе на вопрос 219845.