En 1999, l’avènement d’Abdelaziz Bouteflika à la présidence en Algérie laissait espérer un règlement du conflit. Le plaidoyer du Maroc en faveur d’une autonomie du Sahara a produit ses effets, la France, les États-Unis et l’Espagne le soutiennent. Il reste à convaincre l’Algérie de s’y résigner. En mars 2005, la rencontre entre le président Abdelaziz Bouteflika et le roi du Maroc, Mohamed VI, apparaît comme les prémisses du dégel. La presse se fait l’écho de la rumeur annonçant la réouverture de la frontière entre l’Algérie et le Maroc, premier geste symbolique des retrouvailles. Dans la foulée, la Libye, qui préside l’UMA (Union du Maghreb arabe), annonce la date d’un sommet des chefs d’État les 25-26 mai 2005 à Tripoli. L’enthousiasme est de courte durée. Mohamed VI annonce qu’il ne participera pas au sommet, provoquant de fait son annulation. Les propos tenus par A. Bouteflika, quelque temps auparavant, sur le droit des Sahraouis à l’autodétermination servent de prétexte pour remettre en question les tentatives de réconciliation algéro-marocaine. Le discours officiel de l’Algérie sur le Sahara n’a pas changé. Comme le rappelle le ministre délégué chargé des Affaires maghrébines et africaines, et africaines, M. Messahel, en mars 2006, « La résolution de conflit réside dans l’exercice par le peuple sahraoui de son droit sacré à l’autodétermination… C’est la position définitive de l’Algérie… La situation de blocage revient, en premier lieu, à l’ONU qui doit bouger et prendre ses responsabilités. ». Position que souligne Mohamed Bedjaoui, ministre des Affaires étrangères, en juin 2006, dans le journal Liberté, en insistant sur le plan Baker et le soutien à la résolution 1 675 sur le droit à l’autodétermination du peuple sahraoui…Pour le Maroc, le retour de l’abondance financière en Algérie explique son désintérêt économique pour la région. En fait, la fermeture de la frontière coûte plus cher à Rabat qu'à Alger. En effet, à la faveur du troisième choc pétrolier, l’Algérie dispose d’un fonds de réserve estimé en 2010 à 150 milliards de dollars. Redevenue riche, elle a de nouveau les moyens de défendre ses prétentions.

Les deux pays se sont engagés dans une mini guerre froide, une course à l’armement qui n’augure rien de bon pour le développement politique de la région.  Du point de vue marocain, le renouveau économique de l’Algérie se traduit par un regain de tension. Pour l’instant, le risque d’une guerre ouverte est inenvisageable, tout comme une guerre par procuration. Comme le souligne James Baker (TelQel Magazine, Maroc, août 2004) : « l’Algérie et le Maroc collaborent étroitement avec les États-Unis dans leur guerre contre le terrorisme. Il est donc particulièrement difficile pour Washington de favoriser l’un ou l’autre parce qu’il veut rester proche des deux… L’Algérie est très forte, le Maroc a remporté la guerre, le Polisario, sous occupation, est faible. Le conflit armé n’est pas à l’ordre du jour. Tant que l’Algérie dit au Polisario de ne pas combattre, il ne va pas le faire ». De plus, si le Maroc et l’Algérie ne parviennent toujours pas à s’entendre, ils ont développé des relations bilatérales avec la France, l’Espagne et les États-Unis. Or ces derniers oeuvrent à un réchauffement des relations entre l’Algérie et le Maroc (la suppression par le Maroc des visas pour les Algériens participe de ces gestes qui peuvent apaiser les relations). Pour des raisons diverses, la France, l’Espagne et les États-Unis s’efforcent d’entretenir une relation équilibrée avec les deux protagonistes. Mais pour le Maroc, l’Algérie d’Abdelaziz Bouteflika cherche à rejouer l’Algérie de Houari Boumediene (1965-1979), une puissance régionale, dopée par les hydrocarbures, soucieuse de ne pas abdiquer face à la victoire remportée par Maroc dans le Sahara.