X. (geb. 1981) will als staatenloser Palästinenser im Flüchtlingslager Bar Elias in Beirut geboren sein und seit seinem zweiten Lebensjahr in Algerien gelebt haben. Am 11. März 2004 lehnte das Bundesamt für Flüchtlinge sein Asylgesuch ab und forderte ihn auf, die Schweiz zu verlassen, was er nicht tat. Vom 21. Dezember 2004 bis zum 21. Dezember 2006 verbüsste X. mehrere Gefängnisstrafen im Zusammenhang mit verschiedenen Diebstählen und Betäubungsmitteldelikten. Abklärungen bei den algerischen Behörden zu seiner Identität blieben ohne Erfolg.

Am 17. Januar 2007 nahm das Ausländeramt des Kantons St. Gallen X. in Durchsetzungshaft. Der Einzelrichter der Verwaltungsrekurskommission des Kantons St. Gallen genehmigte diese am 19. Januar 2007 und verlängerte sie in der Folge - jeweils in Schritten von zwei Monaten - bis zum 16. Februar 2008. Ein weiteres Gesuch des Ausländeramts, die Haft um zwei Monate zu verlängern, wies er am 14. Februar 2008 ab: Die Fortsetzung der Durchsetzungshaft erscheine trotz Fehlens von Haftbeendigungsgründen nicht mehr verhältnismässig, da der "Haftvollzug seinen Zweck bis zur gesetzlichen Haftbeendigung in fünf Monaten voraussichtlich nicht mehr erreichen" werde. Es fehlten konkrete Anhaltspunkte dafür, dass X. "innerhalb der gesetzlich maximal zulässigen Haftdauer von 18 Monaten zu einer Änderung seines Verhaltens gebracht werden" könne.

Das Bundesgericht heisst die vom Bundesamt für Migration hiergegen eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten gut und hebt den haftrichterlichen Entscheid auf.

1.1 Das Bundesamt für Migration ist im Bereich der ausländerrechtlichen Zwangsmassnahmen zur Behördenbeschwerde legitimiert, falls es um die Klärung einer Rechtsfrage eines tatsächlich bestehenden Einzelfalls mit Auswirkungen auf künftig ähnlich gelagerte Sachverhalte geht (vgl. Art. 89 Abs. 2 lit. a BGG in Verbindung mit Art. 14 Abs. 2 OV-EJPD [SR 172.213.1]; BGE 129 II 1 E. 1.1 S. 4). Das ist insbesondere dann der Fall, wenn sich eine neue Rechtsfrage stellt oder wenn es gilt, einer drohenden bundesrechtswidrigen Rechtsentwicklung in der kantonalen Praxis Einhalt zu gebieten (vgl. die Urteile 2A.709/2006 vom 23. März 2007, E. 2.1, und 2A.748/2006 vom 18. Januar 2007, E. 2.2). Diese Voraussetzungen sind hier erfüllt: Zwar hat sich das Bundesgericht in BGE 134 I 92 ff. mit der EMRK-Konformität und der Problematik der Verhältnismässigkeit der Durchsetzungshaft bereits auseinandergesetzt, doch stand der vorliegend zu prüfende Aspekt in jenem Verfahren nicht im Vordergrund.

1.2 Der Entscheid der Verwaltungsrekurskommission des Kantons St. Gallen ging dem Bundesamt für Migration am 22. Februar 2008 zu. Dieses hat seine Beschwerde - unter Inanspruchnahme des Friststillstands über Ostern (Art. 46 Abs. 1 lit. a BGG) - am 28. März 2008 eingereicht. Die I. öffentlich-rechtliche Abteilung hat entschieden, dass der gesetzliche Friststillstand von Art. 46 Abs. 1 BGG bei der strafprozessualen Haft nicht zur Anwendung komme (vgl. BGE 133 I 270 E. 1.2.2); diese Rechtsprechung kann indessen nicht auf die ausländerrechtlichen Festhaltungen übertragen werden: Der Friststillstand gilt nicht in Verfahren betreffend aufschiebende Wirkung und andere vorsorgliche Massnahmen sowie in der Wechselbetreibung und auf dem Gebiet der internationalen Rechtshilfe (Art. 46 Abs. 2 BGG). Die ausländerrechtlichen Zwangsmassnahmen fallen unter keine dieser Ausnahmen. Art. 112 Abs. 2 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20; in Kraft seit dem 1. Januar 2008) sieht ausdrücklich vor, dass die Bestimmungen über den Friststillstand einzig bei der bundesrechtlichen Wegweisung am Flughafen (Art. 65 AuG) und beim Empfangsstellenverfahren (Art. 76 Abs. 1 lit. b Ziff. 5 AuG) keine Anwendung finden; nach Art. 112 Abs. 1 AuG richtet sich das Verfahren der Bundesbehörden nach den allgemeinen Bestimmungen der Bundesrechtspflege, womit Art. 46 BGG vor Bundesgericht zur Anwendung kommt. Auf die Beschwerde ist somit einzutreten.

2.1 Umstritten ist, ob der Haftrichter davon ausgehen durfte, dass die Durchsetzungshaft des Beschwerdegegners nicht (mehr) verlängert werden konnte, da dies unverhältnismässig war. Die Frage ist mit dem Bundesamt für Migration zu verneinen:

2.2.1 Zweck der Durchsetzungshaft ist es, die ausreisepflichtige Person in jenen Fällen zu einer Verhaltensänderung zu bewegen, in denen nach Ablauf der Ausreisefrist der Vollzug der rechtskräftig gegen sie angeordneten Weg- oder Ausweisung - trotz entsprechender behördlicher Bemühungen - ohne ihre Kooperation nicht (mehr) möglich erscheint (vgl. Art. 78 AuG). Der damit verbundene Freiheitsentzug stützt sich sowohl auf Art. 5 Ziff. 1 lit. f (Haft zur Sicherung eines schwebenden Ausweisungsverfahrens) als auch auf Art. 5 Ziff. 1 lit. b EMRK (Haft zur Erzwingung einer durch das Gesetz vorgeschriebenen Verpflichtung). Die Durchsetzungshaft bildet das letzte Mittel, wenn und soweit keine andere Massnahme (mehr) zum Ziel führt, den illegal anwesenden Ausländer auch gegen seinen Willen in seine Heimat verbringen zu können. Sie darf nach dem Willen des Gesetzgebers bis zu 18 Monaten dauern (BGE 134 I 92 E. 2.1 und 2.3.1; BGE 133 II 97 E. 2.2 S. 99 f. [zu Art. 13g ANAG]).

2.2.2 Nach der Rechtsprechung muss jeweils aufgrund der Umstände im Einzelfall beurteilt werden, ob die Durchsetzungshaft (noch) geeignet bzw. erforderlich erscheint und nicht gegen das Übermassverbot verstösst (BGE 134 I 92 E. 2.3.2; BGE 133 II 97 E. 2.2 S. 100 [zu Art. 13g ANAG]). Dabei ist dem Verhalten des Betroffenen, den die Papierbeschaffung allenfalls erschwerenden objektiven Umständen (ehemalige Bürgerkriegsregion usw.) sowie dem Umfang der von den Behörden bereits getroffenen Abklärungen Rechnung zu tragen und zu berücksichtigen, wieweit der Ausländer es tatsächlich in der Hand hat, die Festhaltung zu beenden, indem er seiner Mitwirkungs- bzw. Ausreisepflicht nachkommt (BGE 134 I 92 E. 2.3.2 S. 97 [zu Art. 13g ANAG]).

2.2.3 Der Beschwerdegegner hat sich strikte geweigert, in sein Heimatland zurückzukehren und bei der Abklärung bzw. Erstellung seiner Identität in irgendeiner Weise mitzuwirken. Er erklärte am 6. Februar 2008, nicht bereit zu sein, sein renitentes Verhalten aufzugeben; er nehme vielmehr eine weitere Verlängerung der Durchsetzungshaft in Kauf. Entgegen der Annahme des Haftrichters konnte hieraus nicht geschlossen werden, diese Zwangsmassnahme könne ihr Ziel (überhaupt) nicht mehr erreichen: Der Beschwerdegegner wurde seit 13 Monaten administrativ festgehalten; die Haft konnte bis zu einer Dauer von 18 Monaten verlängert werden und hätte - bei einer allenfalls anschliessend möglichen Ausschaffungshaft - insgesamt bis zu 24 Monaten dauern können (vgl. Art. 79 AuG). Vor der Anordnung der Durchsetzungshaft hatten die Behörden alles Denkbare vorgekehrt, um den Vollzug der Wegweisung zu organisieren, doch scheiterten ihre Bemühungen immer wieder an der unkooperativen Haltung des Betroffenen. Dieser verfügte in der Schweiz über keine sozialen Beziehungen (Familie usw.), denen im Rahmen der Interessenabwägung bei der Haftverlängerung Rechnung zu tragen gewesen wäre; er hatte sich seit seiner Wegweisung auch nicht klaglos verhalten, wurde er hier doch wiederholt straffällig (Diebstahl, Betäubungsmittelhandel usw.). Seiner Durchsetzungshaft war denn wiederum eine Tätlichkeit gegen einen Mitbewohner an dem ihm zugewiesenen Aufenthaltsort vorausgegangen. Beim Beschwerdegegner handelte es sich schliesslich auch nicht um eine "besonders schutzbedürftige" Person, welche wegen ihres Alters, Geschlechts oder Gesundheitszustands spezieller Betreuung bedurft hätte, die ihr nicht in einer Vollzugsanstalt gewährt werden konnte. Damit sprachen keine überwiegenden Gründe gegen die Verlängerung der Durchsetzungshaft um die vom Ausländeramt beantragten zwei Monate.

2.2.4 Was der Haftrichter hiergegen einwendet, überzeugte - jedenfalls zum Zeitpunkt des angefochtenen Entscheids, auf den abzustellen ist - nicht: Dass sich der Betroffene (immer noch) unkooperativ zeigt, ist Voraussetzung, um die Festhaltung überhaupt verlängern zu können, und insoweit sachimmanent, als der Durchsetzungshaft (auch) die Funktion einer Beugehaft zukommt (vgl. BGE 134 I 92 E. 2.3.1). Allein die Tatsache, dass der Beschwerdegegner sich konsequent geweigert hat, seine Identität offenzulegen oder zu deren Klärung beizutragen, konnte noch nicht bedeuten, dass die Durchsetzungshaft nicht mehr geeignet war, das angestrebte Ziel zu erreichen. Das mutmassliche künftige Verhalten des Betroffenen ist jeweils aufgrund sämtlicher Umstände abzuschätzen. Ein erklärtes konsequent unkooperatives Verhalten bildet dabei nur einen unter mehreren zu berücksichtigenden Gesichtspunkten, andernfalls die Festhaltung umso weniger angeordnet werden könnte, je renitenter sich die betroffene Person zeigt und je stärker sie versucht, ihre Ausschaffung zu hintertreiben (BGE 134 I 92 E. 2.3.2 S. 97).

2.2.5 Dass der Beschwerdegegner jeweils keine mündliche richterliche Haftüberprüfung verlangt hat, ist nicht entscheidend: Es steht dem Betroffenen frei, dies zu tun, ohne dass daraus etwas zu seinen Gunsten oder Ungunsten abgeleitet werden darf. Auch eine Unterscheidung - wie sie der Haftrichter in seiner Vernehmlassung vorschlägt - danach, ob die Identität des Betroffenen erstellt ist und die Rückführung (nur noch) an der Unmöglichkeit eines Sonderflugs scheitert oder aber noch keinerlei bestätigte Angaben zu seinen Personalien vorliegen, überzeugt nicht. Die Verhältnismässigkeit ist - wie dargelegt - jeweils im Einzelfall aufgrund der konkreten Umstände zu überprüfen; die Zwangsmassnahmen können insgesamt bis zu 24 Monaten dauern, wobei nach einer (erfolglosen) Durchsetzungshaft - etwa bei allfälligen Verhandlungen mit dem Heimatstaat bezüglich einer zwangsweisen Rückführung - eine anschliessende Ausschaffungshaft nicht ausgeschlossen ist. Beim Beschwerdeführer wäre in diesem Fall eine weitere Festhaltung von insgesamt 11 Monaten möglich gewesen, womit der Umstand, dass seine Personalien noch nicht erstellt waren, für seine Freilassung nicht ausschlaggebend sein konnte. Das öffentliche Interesse, die Durchsetzungshaft zu verlängern, um die rechtskräftige Wegweisung vollziehen zu können, überwog (zumindest) im Februar 2008 noch jenes des Beschwerdegegners, auf freien Fuss gesetzt zu werden, auch wenn die Verhältnismässigkeit der Durchsetzungshaft desto kritischer zu hinterfragen ist, je länger sie dauert. Die Durchsetzungshaft unterliegt zudem in dem Sinn dem Beschleunigungsgebot, dass die Behörden regelmässig von Amtes wegen zu prüfen haben, ob die Ausschaffung tatsächlich vollzogen werden könnte, falls der Betroffene bereit wäre, zu kooperieren; überdies müssen sie ihn bei seinen Bemühungen, die erforderlichen Papiere zu beschaffen, jeweils aktiv unterstützen (BGE 134 I 92 E. 2.3.1 S. 96).