Никита Хониат описывает один случай этой кампании: Алексей вошел в пограничную деревушку под названием Мелангея, жители которой приветствовали его как императора, но также проявили уважение и к лже-Алексею II, так что было неясно, на чьей они стороне. Они сказали Алексею Ангелу, что этот молодой человек – чудо, и, как только император увидит его, он тоже будет приветствовать его. Император ответил, что настоящий Алексей II умер, а это – всего лишь самозванец, добавив, что даже если этот человек – подлинный претендент, то у него самого больше прав на трон, потому что он им владеет. Крестьяне тут же поймали его на слове, сказав, что даже он не абсолютно уверен в том, что Алексей II мертв. Алексей III был вынужден прекратить спор.
Новый военачальник Контостефан избегал всяких боевых столкновений с лже-Алексеем, и борьба затягивалась. Упоминается, что весной 1196 г. полководец по имени Ватац противостоял лже-Алексею в Вифинии, но в конечном счете узурпатор был убит посторонним человеком у Гангры (Чанкыры) при неизвестных обстоятельствах. А в это время до конца 1196 г. Мухий ад-Дин торговался по поводу суммы денег, которая должна была ему выплачиваться. Оказывая помощь лже-Алексею, он воспользовался случаем захватить византийский город Дадивру (вероятно, современный Дев-рек) в Пафлагонии, который он осаждал четыре месяца. Император обещал поддержку, но пафлагонские провинциалы не осмелились прийти на помощь городу, так что голод и турецкие осадные орудия посеяли хаос среди его жителей. В конце концов, пришла спасательная армия под командованием Феодора Враны, Андроника Катакалона и Феодора Казана, вероятно, из Гераклеи Понтийской и встала лагерем на горе Баба. Турки узнали о ее подходе и устроили засаду, в которую и попали безрассудные молодые полководцы. Византийское войско было рассеяно, а двух захваченных военачальников – вероятно, Катакалона и Казана – провели связанными вокруг стен Дадивры. Жители города пришли в отчаяние, и было достигнуто соглашение, согласно которому любой желающий мог уйти из города вместе со своей семьей и всем, что можно унести, а остальные должны были остаться и платить налоги туркам. Этот договор был исполнен буквально; те горожане, которые предпочли уйти, рассеялись по другим пафлагонским городам, а турки заселили Дадивру заново. Вскоре после этого, несмотря на утрату Дадивры, Алексей III наконец согласился выплатить полностью сумму, которую изначально требовал Мухий ад-Дин. Эмир Анкары прислал императору отряд турецких солдат, которые в 1197 г. хорошо себя показали при штурме Просакона.
Тем временем возникла проблема, созданная главным образом самим Алексеем и связанная с младшим сыном султана Коньи Кылыч-Арслана Гияс ад-Дином Кей-Хосровом I. В знак уважения султан Египта прислал Алексею двух арабских скакунов, но по дороге через Малую Азию их на время «позаимствовал» Кей-Хосров, чтобы испытать их качества на скачках. Когда один из коней вывихнул колено в тренировочном забеге, турок написал Алексею, прося прощения за то, что забрал животных и боялся отсылать одного коня из-за непригодности другого. Он пообещал отправить обоих коней, как только поправится травмированный жеребец. Отказавшись принимать извинения, Алексей чуть не зад охнулся от гнева и пригрозил войной. В качестве немедленного возмездия он приказал конфисковать товары всех купцов, византийских или турецких, которые вели торговлю с Коньей. Эти товары он распределил среди своих фаворитов. Кей-Хосров не мог спустить такое оскорбление и без промедления повел свое войско в долину Меандра – вероятно, это было в 1196 г. Там он захватил Карию (вероятно, это современная Гейсе) и Танталос (возможно, на реке Дандал-Су) и двинулся на Антиохию – ключевую крепость в среднем течении Меандра. Когда он приблизился к ней ночью, он услышал звуки шумного свадебного веселья, похожие на звуки, которые издают солдаты, готовясь к войне. Не желая получить отпор, он вернулся назад вместе с пленниками, насчитывавшими, по непроверенным данным, пять тысяч человек, с которыми он обошелся хорошо: они получили землю в окрестностях Филомелиона и семена пшеницы, а также освобождение от налогов на пять лет. Эта колония, по словам Никиты Хониата, превратилась в такое процветающее поселение, что многие другие византийцы добровольно присоединялись к ней.