Возникали и вообще абсурдные ситуации. В Брюсселе на встрече министров обороны стран НАТО с партнёрами македонский министр недоумевал по поводу того, что язык, на который осуществлялся перевод, обозначался как «бывшей Югославской Республики македонский».
По состоянию на 2016 год вопрос так и не был решён, несмотря на многочисленные переговоры между сторонами при ооновском посредничестве.
Одной из самых трудных и болезненных проблем молодой России стали отношения со странами Балтии. В бесправном положении оказалось многочисленное русское население Эстонии и Латвии (в Литве, где русских около восьми процентов, их притеснять не стали). Предстояло решить вопрос и о выводе российских войск с территории Балтии. Вокруг этих тем в России бушевали нешуточные политические страсти. Для переговоров по выводу войск были созданы соответствующие российские государственные делегации. Мне приходилось подключаться лишь для «разруливания» конкретных ситуаций.
В сентябре 1992 года нацелились на подписание в Москве договора о выводе войск из Литвы. Переговоры шли трудно. В какой-то момент мне пришлось присоединиться к главе делегации Виктору Фёдоровичу Исакову в литовском посольстве в Москве для того, чтобы помочь подтолкнуть дело. Атмосферу переговоров никак нельзя было назвать дружественной. Когда поздним вечером я, пытаясь завершить согласование одного из вопросов, предложил поставить точку и выпить шампанского, глава литовской делегации отреагировал неожиданно мрачно: «Вот так же и Риббентроп с Молотовым пили шампанское». Мы явно не тянули на этих персонажей из 1939 года.
Задача российской делегации не стала легче, когда выяснилось, что два офицера из министерства обороны с ведома своего руководителя провели параллельные переговоры с литовцами о выводе войск и согласовали проект соглашения. Я встретился с ними. Офицеры в их представлении преследовали самые благие цели: боролись с наследием советской военной бюрократии. Однако в политике они были несведущи. Например, не понимали значения включённого ими в текст соглашения положения о готовности России обсуждать претензии Литвы об ущербе, нанесённом в период «оккупации» (в Вильнюсе тогда назывались астрономические цифры — до 140 млрд долларов). После такой «уступки» вычистить положение о возмещении ущерба из договора с Литвой стало особенно трудно. В итоге данный вопрос был вынесен из текста договора и запрятан куда-то в примечание. Всё, казалось бы, готово к торжественной церемонии в Кремле. Делегации собрались, ожидая руководителей — Ельцина и Ландсбергиса, но те задерживались. Шеф протокола президента Владимир Николаевич Шевченко предложил министру обороны Грачёву и мне (Козырев находился в отъезде) пройти в зимний сад, где беседовали Ельцин с Ландсбергисом. К моему удивлению, боевой генерал не продемонстрировал той храбрости, которой от него можно было бы ожидать. «Пойдёмте, Павел Сергеевич», — я потянул за рукав министра.