Iniziò così la seconda fase della Missione Bilaterale Interforze di Assistenza alla Polizia albanese, alla quale era previsto che l'Arma partecipasse con 7 unità, la Polizia di Stato con 12 e la Guardia di Finanza con 8, per un totale di 27 elementi, oltre al personale delle unità navali del Nucleo Frontiera Marittima della Guardia di Finanza (nell'organigramma della missione), compreso fra le 50 e le 70 unità. Erano altresì previsti: un Nucleo centrale (che avrebbe svolto, fin dall'inizio e per tutta la durata della missione, oltre all'azione di direzione e di controllo di tutte le attività, il compito di consulenza ed assistenza in generale nei confronti dei vertici delle competenti amministrazioni albanesi); Nuclei di consulenza e assistenza sul territorio; Nuclei Navali di manovra, localizzati nel porto di Durazzo e assegnati alla Guardia di Finanza. Alla fine di questa seconda fase, la missione si costituiva ufficialmente.
Il 12 novembre 1997 il Reparto Carabinieri Albania, composto da 2 ufficiali, 4 marescialli e un appuntato, si era completamente costituito in territorio albanese. L'Arma centrava il suo intervento sull'assistenza alla Polizia albanese, esclusivamente sulla terraferma. I settori di competenza erano speculari a quelli della Missione Mape-Ueo (Multinational Advisors Police Element) e cioè la tutela dell'ordine pubblico, il controllo del territorio, il sostegno logistico, l'organizzazione e il metodo: occorreva quindi un coordinamento con quella missione.
La presenza dell'Arma nella Bilaterale è sempre stata molto attiva, sia operativamente che dal punto di vista dell'assistenza nella redazione e applicazione dell'ordinamento. Nel primo semestre di attuazione, oltre all'opera svolta sul territorio albanese, i Carabinieri provvidero a pianificare dei corsi per una decina di elementi presso la Scuola Sottufficiali di Firenze.
Nella cornice di questa missione, essi si sono occupati in particolare della Guardia Repubblicana (assimilabile ai Corazzieri per compiti istituzionali), dando opera di consulenza e assistenza in via esclusiva anche se la Francia e la Turchia dimostravano molto interesse ad intervenire a loro volta, con elementi delle rispettive Gendarmerie. Il rapporto con la Guardia era iniziato fattivamente nell'agosto del 1998. A favore di questo Corpo erano stati svolti corsi basici e intermedi con particolari programmi che prevedevano anche, ad esempio, lo studio del cerimoniale e dei servizi di scorta e sicurezza delle residenze ufficiali: l'Arma cedette a favore della Guardia armi, mezzi e materiali.
All'atto del terzo rinnovo del Protocollo d'Intesa, nel 1999, l'Arma aveva dislocate per questa missione in Albania 7 unità, con i seguenti compiti: l'ufficiale superiore comandava il contingente dei Carabinieri, il secondo ufficiale era il responsabile di un Nucleo territoriale, 3 marescialli erano istruttori, 2 operavano nelle Questure e uno nei Nuclei radiomobili di Tirana e Durazzo, insieme ad un appuntato. In seguito al terzo rinnovo fu deciso che l'Arma avrebbe incrementato il proprio personale di 5 unità e che l'istituzione del Nucleo territoriale di Scutari avrebbe richiesto la presenza di un ufficiale dei Carabinieri in qualità di Comandante.
Dal 9 aprile 1999 l'Arma ebbe un incremento di 20 unità, il che portò a un totale di impegno di 57 militari. Da quella data fu operativa a Kukes, per l'emergenza dell'afflusso dei rifugiati kosovari, una squadra composta da 11 elementi della Missione Interforze (tra i quali 5 dell'Arma, 4 della Polizia di Stato e 2 della Guardia di Finanza), agli ordini di un ufficiale dei Carabinieri, quale punto di riferimento per la componente italiana della Protezione Civile, del Volontariato e della Croce Rossa e per il collegamento tra queste e la Polizia locale albanese. La squadra avrebbe terminato il proprio impegno quando la Missione Arcobaleno, allora costituita, avesse definito le ulteriori fasi operative. Nel quadro della Bilaterale, per quella particolare emergenza, erano stati fatti affluire a Tirana quattro Moduli operativi, forti di ulteriori 103 elementi tra Polizia di Stato e Carabinieri.

Per riassumere e meglio comprendere la situazione, nell'aprile 1999 la Bilaterale si componeva di: un Nucleo centrale a Tirana; quattro Nuclei territoriali a Tirana, Valona, Fier e Lezhe; due Nuclei di Frontiera marittimi a Durazzo e all'Isola di Saseno; quattro Moduli operativi, di cui due dell'Arma, a Durazzo e a Kavaje; una Squadra interforze operante a Kukes sotto il comando dell'Arma; un Ufficio di Polizia Criminale a Tirana, composto da personale dell'Arma, della Polizia di Stato e della Guardia di Finanza. Ogni Nucleo territoriale e ogni Modulo operativo aveva una composizione interforze ed era omogeneo.
I Moduli operativi per l'emergenza dei rifugiati kosovari vennero poi integrati nella Bilaterale. Infatti nel quadro della Missione Arcobaleno vi furono due Nuclei dei Carabinieri (42 unità), responsabili per la sicurezza di due campi profughi (Kavaje e Rrashbull), con il compito di fornire assistenza anche nell'organizzazione e gestione dei centri di raccolta dei profughi. Il 7 aprile 1999 erano state inviate 22 unità, e il 9 aprile, come detto, altre 20. Alla Missione Arcobaleno parteciparono, dal 7 aprile al 4 agosto 1999, 2 ufficiali, 10 marescialli, 32 tra brigadieri appuntati e carabinieri, unitamente al personale della Polizia di Stato. Conclusasi la missione il 4 agosto, i carabinieri confluirono funzionalmente, a far data dal 12 agosto fino al 10 settembre successivo, nella Bilaterale Interforze, per essere impiegati presso i Nuclei territoriali già esistenti di Tirana e Scutari e in quelli costituendi di Durazzo e di Lezhe, al fine di rafforzare e meglio identificare l'impegno dell'Arma in quell a missione. Dal 1° settembre avrebbe operato anche una Compagnia di Carabinieri con compiti di polizia militare nell'ambito della Commz-W Kfor. Alla fine della Missione Arcobaleno, per la Bilaterale Interforze rimasero in territorio albanese, in totale, 56 unità dell'Arma.
Nel mese di settembre del 1999 iniziò lentamente il ritiro del contingente dei Carabinieri, nel quadro generale del ridimensionamento della missione. Una prima aliquota di 22 unità rientrò nella prima decade del mese di settembre; nella seconda decade ne rientrarono altre 22, mentre 12 unità rimanevano in forza alla Bilaterale. Nel gennaio 2000 fu decisa una proroga ancora per 180 giorni, contraendo l'organico della missione da 112 a 99 unità, ripartite in 10 dei Carabinieri, 57 della Guardia di Finanza, 22 della Polizia di Stato e 10 dell'area interforze di Polizia. Obiettivo di quel particolare rinnovo fu il completamento dei programmi di consulenza ed assistenza tecnica in corso.
Vari, significativi risultati sono stati raggiunti: tra l'altro, il 21 giugno 2001 si è inaugurata a Tirana, realizzata con il supporto della Bilaterale, la Centrale Operativa allestita presso la Direzione della Polizia albanese, punto di coordinamento per i necessari servizi di controllo in tutto il territorio. L'impegno della Polizia locale comprende anche importanti recuperi di armi da guerra, oltre ad attività di controllo dell'ordine pubblico e del rispetto della legalità. In questo quadro sono da ricondursi alcune operazioni di contrasto al contrabbando di merci e alla riduzione in schiavitù di esseri umani, oltre che alla attività criminosa della gestione dei clandestini.