SUR CE :
Sur la recevabilité de l'appel
En l'espèce, en application de l'article R743-10 du CESEDA, l'appel est recevable pour avoir été fait dans les termes et délais légaux.
Sur la fin de non-recevoir
Sur le défaut de pièces utiles
Aux termes de l'article R.743-2 du CESEDA, à peine d'irrecevabilité, la requête est motivée, datée et signée, selon le cas, par l'étranger ou son représentant ou par l'autorité administrative qui a ordonné le placement en rétention. Lorsque la requête est formée par l'autorité administrative, elle est accompagnée de toutes pièces justificatives utiles, notamment une copie du registre prévu à l'article L. 744-2.
La requête en deuxième prolongation doit être motivée en droit et en fait.
Doivent être considérées des pièces justificatives utiles dont la production conditionne la recevabilité de la requête les pièces qui sont nécessaires à l'appréciation par le juge des éléments de fait et de droit dont l'examen lui permet d'exercer son plein pouvoir.
Il est constant que l'ordonnance de la juridiction d'appel ayant confirmé la première prolongation constitue une pièce utile indispensable à l'occasion d'une demande de deuxième prolongation, en ce qu'elle permet au juge saisi de vérifier, d'une part, l'existence et le caractère exécutoire de la décision judiciaire prolongeant la privation de liberté, et d'autre part, la réalité de sa notification régulière à l'intéressé, laquelle conditionne l'ouverture des voies de recours et fixe le point de départ du délai de la seconde prolongation.
L'appelant soutient que la requête préfectorale du 14 avril 2026 était irrecevable en ce qu'elle n'était pas accompagnée des ordonnances rendues à l'occasion du précédent placement en rétention de son client intervenu en 2025, ni de la preuve régulière de leur notification à l'intéressé.
Toutefois, le premier juge a retenu, à juste titre, que la décision constitutionnelle du 16 octobre 2025 avait abrogé l'article L. 741-7 du CESEDA imposant au juge le contrôle du cumul des périodes de rétention, de sorte que le contrôle ainsi supprimé rendait sans objet l'obligation de produire les pièces relatives à la précédente rétention de 2025.
En outre, il ressort des pièces du dossier que l'arrêté de placement en rétention du 16 mars 2026, joint à la requête préfectorale, rappelle expressément et de façon détaillée le précédent placement de l'intéressé au CRA le 19 mars 2025 ainsi que le maintien en rétention pour une durée totale de 90 jours, satisfaisant ainsi aux exigences du contrôle institué par le Conseil constitutionnel. La mesure d'éloignement fondant la présente rétention, soit l'interdiction judiciaire du territoire français de cinq années prononcée le 19 août 2025, est distincte de celle fondant la précédente rétention de 2025, ce qui exclut l'application de la décision constitutionnelle du 16 octobre 2025.
Par ailleurs, s'agissant de la notification de l'ordonnance de la Cour d'appel du 25 mars 2025, il convient de relever que l'arrêté de placement en rétention joint à la requête renseigne suffisamment le juge sur le déroulé de la procédure antérieure et que la base légale de la présente mesure de rétention est autonome et indépendante de la précédente. Dès lors, l'absence de production de la preuve formalisée de cette notification, si elle peut être regrettable, ne prive pas le juge de la possibilité d'exercer son contrôle effectif sur la mesure en cours.
En conséquence, le moyen sera écarté et l'ordonnance étant confirmée sur ce point.
Sur le défaut d'actualisation de la fiche de rétention
L'article L. 744-2 du CESEDA impose la tenue d'un registre dans chaque centre de rétention, mentionnant pour chaque étranger placé les décisions le concernant, les notifications dont il a fait l'objet, les visites reçues, les soins dispensés ainsi que les incidents survenus durant le placement, ce registre devant être émargé par l'étranger à l'occasion de chaque mention.
L'appelant fait valoir que la fiche de rétention de M. X se disant [P] [K] présentait de multiples irrégularités : absence d'émargements systématiques lors des notifications, mentions incomplètes ou tardives des diligences consulaires, et absence de trace des observations formulées par l'intéressé ou son conseil.
La Cour relève cependant que les irrégularités formelles affectant le registre de rétention ne sauraient entraîner automatiquement l'irrecevabilité de la requête en prolongation, dès lors qu'il n'est pas établi que ces irrégularités ont porté une atteinte substantielle aux droits de l'intéressé, lequel a été régulièrement assisté de son conseil et a pu, par son intermédiaire, faire valoir l'ensemble de ses arguments devant le premier juge comme en appel. Le juge dispose, par ailleurs, des pièces essentielles lui permettant d'exercer son contrôle sur les conditions matérielles et la durée de la rétention.
Ce moyen sera en conséquence écarté.
Sur la prolongation de la rétention
Aux termes de l'article L. 742-4 du CESEDA, le magistrat du siège peut, dans les mêmes conditions qu'à l'article L. 742-1, être à nouveau saisi aux fins de prolongation du maintien en rétention au-delà de trente jours, notamment lorsque la décision d'éloignement n'a pu être exécutée en raison du défaut de délivrance des documents de voyage par le consulat dont relève l'intéressé, ou lorsque la délivrance de ces documents est intervenue trop tardivement pour permettre l'exécution de la décision d'éloignement.
Au stade de la deuxième prolongation, il appartient au juge d'apprécier concrètement l'existence de perspectives raisonnables d'éloignement, au regard des données de la cause à la date à laquelle il statue, en tenant compte notamment de la durée maximale de rétention restant légalement applicable à l'intéressé et des circonstances permettant d'établir qu'il existe une probabilité significative que l'éloignement puisse être mené à bien dans le délai restant. Cette perspective raisonnable ne peut se déduire des seules diligences de l'administration, lesquelles doivent néanmoins présenter un caractère suffisant.
Sur le défaut de diligences suffisantes
Le conseil de l'intimé a soutenu que la préfecture s'était limitée à de simples relances électroniques au consulat d'Algérie les 1er et 13 avril 2026, restées sans réponse, sans mettre en 'uvre de démarches complémentaires telles qu'une procédure de routing ou d'autres mesures de nature à accélérer l'obtention du laissez-passer consulaire.
Il ressort des pièces de la procédure que la préfecture a saisi le CCPD d'[Localité 2] dès le 4 mars 2026, antérieurement au placement en rétention, et a transmis les empreintes au format NIST au consulat d'Algérie à [Localité 3] par courrier du 24 mars 2026, lesquelles ont été adressées par mail le même jour. Deux relances ont ensuite été effectuées les 1er et 13 avril 2026.
Ces diligences, entreprises avant même le placement en rétention et poursuivies avec régularité, présentent un caractère suffisant au regard de l'impératif de célérité posé par la loi. L'administration n'est pas tenue de multiplier les relances dès lors que l'autorité consulaire étrangère a été valablement saisie et qu'elle doit être regardée comme ayant eu connaissance de la demande.
S'agissant de l'absence de demande de routing, ce mécanisme constitue une mesure parmi d'autres et son absence ne caractérise pas à elle seule un défaut de diligences, dès lors que les démarches effectuées par la préfecture auprès du consulat compétent sont documentées, régulières et chronologiquement cohérentes avec la durée de la rétention.
Ce moyen ne peut donc prospérer.
Sur l'absence de perspectives raisonnables d'éloignement
Le conseil de l'intimé a fait valoir que l'absence de réponse du consulat d'Algérie depuis la saisine de mars 2026, dans un contexte de tensions diplomatiques avérées entre la France et l'Algérie, rendait illusoire toute perspective d'éloignement dans le délai légal restant.