Досадный инцидент на острове Крите несколько омрачил, однако, этот успех римского оружия. На Крите уже второй год находился Квинт Метелл, занимавшийся завершением достигнутого им уже в основном покорения этого острова, когда в восточных водах появился Помпей. Возможность столкновения была налицо, так как на основании Габиниева закона власть Помпея параллельно с властью Метелла распространялась на весь растянутый в длину, но нигде не достигающий более 20 миль в ширину остров. Однако Помпей был настолько деликатен, что не назначил на этот остров своего полководца. Но сопротивлявшиеся еще критские общины, видевшие, с какой жестокостью наказывал Метелл их покоренных соотечественников, и слыхавшие, какие мягкие условия предлагал Помпей сдававшимся ему областям южной части Малой Азии, предпочли отправить к нему послов с единогласным изъявлением своей покорности, которое и было принято им в Памфилии, где он находился в то время. Вместе с критскими послами он отправил своего легата Луция Октавия, чтобы уведомить Метелла о заключении договоров и чтобы принять города. Разумеется, это был не товарищеский образ действий, но формальное право было целиком на стороне Помпея, и Метелл поступил безусловно неправильно, когда он, не признавая договор критских городов с Помпеем, продолжал обращаться с ними, как с врагами. Напрасны были протесты Октавия, напрасно он вызвал из Ахайи — так как сам он прибыл без войска — Луция Сизенну, стоявшего там с отрядом войск Помпея. Метелл, не обращая внимания ни на Октавия, ни на Сизенну, осадил Элевферну и взял штурмом Лаппу, где захватил самого Октавия, который был затем с позором отпущен, взятые же вместе с ним критяне были казнены. Так дело дошло до настоящих боев между войсками Сизенны, во главе которых после его смерти стал Октавий, и Метелла; даже после того, как войска его были отправлены обратно в Ахайю, Октавий продолжал войну совместно с критянином Аристионом, и Гиерапитна, где они оба укрылись, была взята Метеллом только после упорнейшего сопротивления.
Таким образом, ярый оптимат Метелл начал на собственный страх настоящую междоусобную войну против демократического главнокомандующего. Насколько расстроены были римские государственные дела, видно из того факта, что эти столкновения привели только к язвительной переписке между обоими полководцами, несколько лет спустя опять мирно и даже «по-дружески» восседавшими друг около друга в сенате.
Во время этих событий Помпей находился в Киликии, подготовляя, казалось, на следующий год поход против критян или, скорее, против Метелла; на самом же деле он дожидался случая для вмешательства в страшно запутанные дела на малоазийском материке. Остатки армии Лукулла, уцелевшие после понесенных потерь и роспуска Фимбриевых легионов, стояли в бездействии на верхнем Галисе, в области трокмов у границы Понтийского царства. Главнокомандующим все еще оставался Лукулл, так как назначенный его преемником Глабрион по-прежнему медлил в Передней Азии. Так же бездействовали три легиона, расположенные в Киликии под начальством Квинта Марция Рекса. Все Понтийское царство опять было во власти царя Митрадата, жестоко наказывавшего за измену ему как отдельных лиц, так и общины, перешедшие на сторону Рима, например, город Евпаторию. Серьезного наступления против римлян восточные цари не предпринимали, — потому ли, что это вообще не входило в их планы, или же потому, как утверждали иные, что высадка Помпея в Киликии побудила царей Митрадата и Тиграна воздержаться от дальнейших действий. Быстрее, чем мог ожидать Помпей, закон Манилия осуществил его тайные надежды: Глабрион и Рекс были отозваны, а наместничества понтийско-вифинское и киликийское с расположенными там войсками, а также ведение войны с Понтом и Арменией с правом по собственному усмотрению решать вопросы войны и мира и заключать союзы с восточными династами были переданы Помпею. Рассчитывая на большие почести и богатую добычу, Помпей охотно отказался от намерения проучить раздражительного и ревниво оберегавшего свои скудные лавры оптимата, оставил поход на Крит и дальнейшее преследование пиратов и назначил свой флот для поддержки наступления, задуманного им против понтийского и армянского царей. Но за этой войной на суше он все же отнюдь не потерял из виду и пиратства, все еще поднимавшего голову. Прежде чем покинуть Азию (691) [63 г.], он распорядился привести в готовность корабли, необходимые для действий против пиратов; по его предложению подобная же мера была принята в следующем году и в Италии, и сенат ассигновал для этого средства. Берега по-прежнему охранялись конными отрядами и небольшими эскадрами. Если же пираты и не были совершенно истреблены, что доказывается походами на Кипр в 696 г. [58 г.] и в Египет в 699 г. [55 г.], о которых будет рассказано дальше, то все же после экспедиции Помпея они никогда уже не поднимали так голову и не могли в такой мере вытеснить римлян с моря, как это имело место в правление разложившейся олигархии.