Sachverhalt:
A. X._ (geb. 1975) ist vietnamesischer Staatsbürger chinesischer Abstammung. Er kam 1991 als Kontingentsflüchtling in die Schweiz, wo ihm am 5. Juli 1991 Asyl gewährt wurde. Zuvor waren seine Familie und er nach Malaysia geflohen und hatten sich dort längere Zeit in einem Lager aufgehalten. Am 20./21. Mai 2002 beging X._ mit Landsleuten in Bern einen Raub, in dessen Verlauf zwei Personen ums Leben kamen. Das Obergericht des Kantons Bern verurteilte ihn am 17. November 2006 wegen Raubes (unter Offenbarung besonderer Gefährlichkeit [Art. 140 Abs. 3 StGB]) sowie (mittäterschaftlich) begangenen mehrfachen Mordes (Art. 112 StGB) zu 15 Jahren Zuchthaus sowie 12 Jahren Landesverweisung. Das Bundesgericht bestätigte diesen Entscheid am 17. Mai 2007 (Urteil 6P.19/2007 und 6S.51/2007 vom 17. Mai 2007).
Am 15. August 2007 wies das Sicherheitsdepartement des Kantons Basel-Stadt X._ aus der Schweiz aus. Am 6. Februar 2009 widerrief das Bundesamt für Migration das Asyl, wogegen X._ erfolglos an das Bundesverwaltungsgericht gelangte. Dieses hielt in seinem Urteil vom 17. September 2010 fest, dass die Aberkennung des Asyls nicht automatisch auch die Aberkennung der Flüchtlingseigenschaft nach sich ziehe; der Verlust des Asyls wirke sich für den Betroffenen deshalb nicht unmittelbar und konkret nachteilig aus, insbesondere könne er sich weiterhin in der Schweiz aufhalten und arbeiten.
B. Am 29. Juni 2012 ist X._ nach Verbüssung von zwei Dritteln seiner Freiheitsstrafe bedingt aus dem Strafvollzug entlassen worden. Das Migrationsamt des Kantons Basel-Stadt nahm ihn am gleichen Tag für drei Monate in Ausschaffungshaft. Der Einzelrichter für Zwangsmassnahmen am Appellationsgericht des Kantons Basel-Stadt bestätigte diese am 29. Juni 2012. Er verwarf die Einwände von X._, dem Vollzug der Ausweisung stünden das Rückschiebungsverbot und sein Flüchtlingsstatus entgegen. Dabei stellte er auf einen Amtsbericht des Bundesamts für Migration (BFM) vom 18. Juni 2012 ab, der zum Schluss gekommen war, dass sich X._ wegen seiner besonderen Gefährlichkeit nicht auf das Rückschiebungsverbot berufen könne (Art. 5 Abs. 2 AsylG [SR 142.31]; Art. 33 Abs. 2 Flüchtlingskonvention [FK; SR 0.142.30]; Art. 3 EMRK; vgl. <ref-ruling> ff.) bzw. ihm heute in seiner Heimat keine Verfolgung mehr drohe.
C. X._ beantragt mit Eingabe vom 2. August 2012, den Entscheid des Haftrichters am Appellationsgericht des Kantons Basel-Stadt aufzuheben; er sei sofort aus der Ausschaffungshaft zu entlassen. Die Ausweisungsverfügung sei nichtig, da im Ausweisungsentscheid vom 15. August 2007 die flüchtlingsrechtliche Problematik überhaupt nicht berücksichtigt worden sei. Im Übrigen fehle es an einem Haftgrund und sei die Ausschaffungshaft unverhältnismässig, da keinerlei Wiederholungsgefahr bestehe; er habe sich seit neun Jahren tadellos verhalten und werde sich den Behörden bei seiner Familie zur Verfügung halten.
Das Justiz- und Sicherheitsdepartement und der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Appellationsgericht des Kantons Basel-Stadt sowie das Bundesamt für Migration beantragen, die Beschwerde abzuweisen und die angeordnete Ausschaffungshaft zu bestätigen. Das Bundesamt weist daraufhin, dass es mit Verfügung vom 16. August 2012 inzwischen die Flüchtlingseigenschaft von X._ aberkannt habe.
X._ hat am 23. August 2012 an seinen Anträgen und Ausführungen festgehalten und verschiedene verfahrensrechtliche Anträge gestellt.

Erwägungen:
1. Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, kann die zuständige Behörde den betroffenen Ausländer zur Sicherstellung von dessen Vollzug unter anderem in Ausschaffungshaft nehmen bzw. in dieser belassen, wenn er andere Personen ernsthaft bedroht oder an Leib und Leben erheblich gefährdet und deshalb strafrechtlich verfolgt wird oder er wegen eines Verbrechens verurteilt worden ist (Art. 76 Abs. 1 lit. b Ziff. 1 in Verbindung mit Art. 75 Abs. 1 lit. g [hierzu das Urteil 2C_304/2012 vom 1. Mai 2012 E. 2.2.1 mit Hinweisen] und lit. h [hierzu das Urteil 2C_455/2009 vom 5. August 2009 E. 2.1] AuG). Der Wegweisungsentscheid muss dabei nicht bereits rechtskräftig sein; es genügt, dass sein Vollzug (z.B. wegen fehlender Papiere) noch nicht möglich, jedoch absehbar erscheint. Der Vollzug der Weg- oder Ausweisung darf sich nicht aus rechtlichen oder tatsächlichen Gründen als undurchführbar erweisen (vgl. Art. 80 Abs. 6 lit. a AuG) und muss mit dem nötigen Nachdruck verfolgt werden (Art. 76 Abs. 4 AuG: "Beschleunigungsgebot"). Die ausländerrechtliche Festhaltung hat zudem als Ganzes verhältnismässig zu sein (vgl. das Urteil des EGMR Jusic gegen Schweiz vom 2. Dezember 2010 [Nr. 4691/06], §§ 67 ff., insbesondere § 73; THOMAS HUGI YAR, Zwangsmassnahmen im Ausländerrecht, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl. 2009, N. 10.114 ff.).
2. Der Beschwerdeführer macht geltend, dass seine Ausweisung vom 15. August 2007 nicht durch eine Ausschaffungshaft gesichert werden könne, da sie sich nicht zu den flüchtlingsrechtlichen Vollzugshindernissen und insbesondere zur Frage des Rückschiebungsverbots äussere; sie habe als nichtig zu gelten.
2.1 Das Verfahren vor dem Haftrichter dient nicht der Überprüfung des Wegweisungsentscheids oder von anderen den Ausländer zur Ausreise verpflichtenden Verfügungen. Der Haftrichter hat sich grundsätzlich nur zu vergewissern, ob (überhaupt) ein Weg- oder Ausweisungsentscheid vorliegt; dessen Rechtmässigkeit bildet nicht Gegenstand seines Verfahrens. Diesbezügliche Einwände sind im Asyl-, Bewilligungs- oder Wegweisungsverfahren durch die jeweils zuständigen Behörden zu prüfen, nicht (erstinstanzlich) durch den Haftrichter (vgl. die Urteile 2C_304/2012 vom 1. Mai 2012 E. 2.1 und 2C_455/2009 vom 5. August 2009 E. 2.3). Die betroffene Person muss sich in diesen Punkten nötigenfalls mit einem Wiedererwägungsgesuch an das Bundesamt oder die zuständige kantonale Ausländerbehörde wenden und hernach den entsprechenden Rechtsweg beschreiten (vgl. <ref-ruling> E. 2; TARKAN GÖKSU, in: Caroni/Gächter/Thurnherr [Hrsg.], Bundesgesetz über die Ausländerinnen und Ausländer [AuG], 2010, N. 14 zu Art. 80; ANDREAS ZÜND, in: Spescha/Thür/Zünd/Bolzli, Migrationsrecht, 3. Aufl. 2012, N. 6 f. zu Art. 80 AuG [e contrario]; HUGI YAR, a.a.O., N. 10.28). Nur wenn der Wegweisungsentscheid offensichtlich unzulässig, d.h. geradezu willkürlich bzw. nichtig erscheint, darf bzw. muss die Haftgenehmigung verweigert werden, da der Vollzug einer in diesem Sinn rechtswidrigen Anordnung nicht mit einer ausländerrechtlichen Zwangsmassnahme sichergestellt werden kann (<ref-ruling> E. 2.2.2 S. 198 mit Hinweisen; <ref-ruling> E. 2c; <ref-ruling> E. 2 S. 58).
2.2 Wie das Bundesgericht festgestellt hat, sind das asyl- bzw. flüchtlings- und das ausländerrechtliche Verfahren jeweils zu koordinieren (vgl. <ref-ruling> E. 3 S. 116 ff.; Urteil 2C_833/2011 vom 6. Juni 2012 E. 2.2). In der Regel ist über die Ausweisung und die Frage, ob ihrem Vollzug asyl- bzw. flüchtlingsrechtliche Gründe entgegenstehen, in einer einzigen Verfügung zu entscheiden. Eine Aufteilung auf zwei Verfahren - analog der Praxis bei der früheren strafrechtlichen Landesverweisung (vgl. <ref-ruling> E. 4f S. 114; <ref-ruling> ff.; <ref-ruling> ff.; <ref-ruling> ff.) - ist indessen nicht bundesrechtswidrig (so die Urteile 2A.313/2005 vom 25. August 2005 E. 3.3 und 2C_87/2007 vom 18. Juni 2007 E. 2.1; siehe auch <ref-ruling> E. 4). Dies gilt insbesondere in Fällen wie dem vorliegenden, in dem zwischen der Ausweisung und dem tatsächlichen Vollzug ein von der Sache her bedingter (Strafvollzug) relativ langer Zeitraum liegt, in dem sich die Verhältnisse verändert haben können (vgl. Urteil 2A.139/1994 vom 1. Juli 1994 E. 4b, bestätigt in den Urteilen 2A.313/2005 vom 25. August 2008 E. 3.3.2 und 2A.51/2006 vom 8. Mai 2006 E. 2.3). Nach der Praxis bildete die unbedingt ausgesprochene (altrechtliche) strafrechtliche Landesverweisung (vgl. alt-Art. 55 StGB [AS 1951 1] i.V.m. mit Ziff. 1 Abs. 2 der Schlussbestimmungen der Änderung des StGB vom 13. Dezember 2002) dementsprechend eine im Sinne von Art. 76 Abs. 1 AuG sicherbare Entfernungsmassnahme, selbst wenn die Vollstreckungsverfügung noch ausstand. Dies muss analog für ausländerrechtliche Ausweisungsentscheide gelten, welche bis zum Inkrafttreten des Ausländergesetzes an die Stelle der Ende 2006 weggefallenen strafrechtlichen Landesverweisung getreten sind (vgl. hierzu das Rundschreiben des Bundesamts für Zuwanderung, Integration und Auswanderung an die Fremdenpolizeibehörden vom 21. Juli 2003 betreffend "Teilrevision des Schweizerischen Strafgesetzbuches. Abschaffung der gerichtlichen Landesverweisung"). Diese müssen ebenfalls weder rechtskräftig noch bereits vollziehbar sein, damit sie mit einer Ausschaffungshaft sichergestellt werden können, falls die Festhaltung dennoch verhältnismässig erscheint und - trotz allfälligen weiteren noch erforderlichen Verfahren - mit dem Wegweisungsvollzug in einem angemessenen Zeitraum gerechnet werden kann (<ref-ruling> E. 1.3 zu Art. 13b ANAG; vgl. auch die Urteile 2A.636/2005 vom 15. November 2005 E. 4 und 2A.13/1999 vom 28. Januar 1999 E. 3).
2.3 Der Beschwerdeführer ist am 15. August 2007 rechtskräftig aus der Schweiz ausgewiesen worden. Er hat im damaligen Verfahren keine Vollzugshindernisse geltend gemacht und nicht auf die erst im Haftverfahren vorgebrachte flüchtlingsrechtliche Problematik hingewiesen. Der Einzelrichter für Zwangsmassnahmen hat die entsprechenden Einwände seinerseits gestützt auf einen Amtsbericht des Bundesamts für Migration eingehend und mit freier Kognition geprüft, obwohl er nach der Rechtsprechung materiell hierzu nur beschränkt zuständig war (vgl. <ref-ruling> E. 2 und das Urteil 2A.47/2007 vom 18. April 2007 E. 2). Er hätte sich damit begnügen können und müssen, festzustellen, dass ein erstinstanzlicher (rechtskräftiger) Ausweisungsentscheid vorliegt, dessen Vollstreckbarkeit - unter Vorbehalt der Nichtigkeit - nicht im Haftverfahren durch ihn zu prüfen sei, sondern durch die hierfür zuständigen Asyl- oder Ausländer(beschwerde)behörden. Der Amtsbericht seitens des Bundesamts für Migration legte nahe, dass keine Weg- oder Vollzugshindernisse vorlagen. Gestützt hierauf musste der Haftrichter die Ausweisungsverfügung hinsichtlich des zu sichernden Entscheids - entgegen der Ansicht des Beschwerdeführers - nicht als offensichtlich unzulässig erachten und er durfte die Haftgenehmigung nicht aus diesem Grund verweigern (vgl. das Urteil 2C_455/2009 vom 5. August 2009 E. 2.3; zum Begriff der Nichtigkeit: <ref-ruling> E. 3.1; <ref-ruling> E. 3.1 und 3.2; <ref-ruling> E. 2.1; <ref-ruling> E. 2; je mit Hinweisen auf die Rechtsprechung).
3.1 3.1.1 Die Ausschaffungshaft soll den Vollzug der Entfernungsmassnahme sicherstellen und muss ernsthaft geeignet sein, diesen Zweck zu erreichen, was nicht (mehr) der Fall ist, wenn die Weg- oder Ausweisung trotz der behördlichen Bemühungen nicht in einem dem konkreten Fall angemessenen Zeitraum vollzogen werden kann. Die Festhaltung hat, weil unverhältnismässig, dann als unzulässig zu gelten, wenn triftige Gründe für solche Verzögerungen sprechen oder praktisch feststeht, dass sich der Vollzug kaum innert vernünftiger Frist wird realisieren lassen (BGE <ref-ruling> E. 4.1.3 S. 61 mit Hinweisen). Eine Beeinträchtigung der öffentlichen Ordnung durch den Betroffenen vorbehalten, welche die Verhältnismässigkeit der Aufrechterhaltung der Haft wegen eines überwiegenden öffentlichen Interesses in einem etwas anderen Licht erscheinen lassen kann, ist dabei nicht notwendigerweise auf die maximale Haftdauer, sondern vielmehr auf einen den gesamten Umständen des konkreten Falles angemessenen Zeitraum abzustellen (BGE <ref-ruling> E. 4.1.3 S. 61 mit Hinweisen). Die Ausschaffungshaft muss verhältnismässig und zweckbezogen auf die Sicherung des Wegweisungsverfahrens ausgerichtet sein; es muss jeweils aufgrund sämtlicher Umstände geklärt werden, ob sie (noch) geeignet bzw. erforderlich erscheint und nicht gegen das Übermassverbot, d.h. das sachgerechte und zumutbare Verhältnis von Mittel und Zweck, verstösst (zur Ausschaffungshaft: <ref-ruling> E. 5.1 S. 5 und unpublizierte E. 7; <ref-ruling> ff.; zur Durchsetzungshaft: <ref-ruling> E. 2.3.2 S. 97; <ref-ruling> E. 2.2 S. 100).
3.1.2 Die entsprechenden Anforderungen an die ausländerrechtliche Festhaltung ergeben sich aus dem Haftzweck, aus Art. 5 Ziff. 1 lit. f EMRK und dem Verhältnismässigkeitsgrundsatz (Art. 5 Abs. 2 und Art. 36 Abs. 3 i.V.m. Art. 10 Abs. 2 BV), aber auch aus der für die Schweiz im Rahmen des Schengen-Besitzstands relevanten sog. "Rückführungsrichtlinie" (Richtlinie 2008/115/EG des Europäischen Parlaments und des Rats vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger, ABl. L 348 vom 24. Dezember 2008 S. 98 ff; vgl. ANDRÉ EQUEY, Änderungen im Bereich der Zwangsmassnahmen im Ausländerrecht aufgrund der Übernahme der EG-Rückführungsrichtlinie durch die Schweiz, AJP 2011 S. 924 ff., dort S. 934): Diese geht grundsätzlich vom Vorrang der freiwilligen Ausreise aus (vgl. Art. 7 RL 2008/115/EG). Machen die Mitgliedstaaten - als "letztes Mittel" - von Zwangsmassnahmen zur Durchführung der Abschiebung von Widerstand leistenden Drittstaatsangehörigen Gebrauch, so müssen diese Massnahmen verhältnismässig sein und dürfen nicht über die Grenzen des Erforderlichen hinausgehen. Sie müssen nach dem einzelstaatlichen Recht im Einklang mit den Grundrechten und unter gebührender Berücksichtigung der Menschenwürde und körperlichen Unversehrtheit der betroffenen Personen erfolgen (Art. 8 Abs. 4 RL 2008/115/EG). Drittstaatsangehörige, gegen die ein Rückkehrverfahren hängig ist, können nur in Haft genommen werden, wenn im konkreten Fall keine anderen, milderen Zwangsmassnahmen wirksam erscheinen (vgl. EQUEY, a.a.O., S. 936); die Haftdauer hat so kurz wie möglich zu sein; sie darf sich nur auf die Dauer der laufenden Abschiebungsvorkehrungen erstrecken, soweit diese mit der gebotenen Sorgfalt vorangetrieben werden (vgl. Art. 15 Abs. 1 RL 2008/115/EG). Erweist sich, dass aus rechtlichen oder anderweitigen Erwägungen keine hinreichende Aussicht auf Abschiebung mehr besteht oder dass die Haftbedingungen nicht mehr gegeben sind, so ist die Haft nicht länger gerechtfertigt und die betroffene Person unverzüglich freizulassen (Art. 15 Abs. 4 RL 2008/115/EG). Als weniger intensive Massnahmen nennt die Richtlinie eine regelmässige Meldepflicht bei den Behörden, die Hinterlegung einer angemessenen Sicherheit, das Einreichen von Papieren und die Verpflichtung, sich an einem bestimmten Ort aufzuhalten (Art. 7 Abs. 3 RL 2008/115/EG; EQUEY, a.a.O., S. 936). In verfahrensrechtlicher Hinsicht sieht sie vor, dass die Rückkehrentscheidung eine sachliche und rechtliche Begründung sowie Informationen über mögliche Rechtsbehelfe enthalten muss und dem Betroffenen das Recht zu gewähren ist, gegen den entsprechenden Entscheid einen wirksamen Rechtsbehelf einlegen zu können (Art. 13 Abs. 1 RL 2008/115/EG).
3.1.2 Die entsprechenden Anforderungen an die ausländerrechtliche Festhaltung ergeben sich aus dem Haftzweck, aus Art. 5 Ziff. 1 lit. f EMRK und dem Verhältnismässigkeitsgrundsatz (Art. 5 Abs. 2 und Art. 36 Abs. 3 i.V.m. Art. 10 Abs. 2 BV), aber auch aus der für die Schweiz im Rahmen des Schengen-Besitzstands relevanten sog. "Rückführungsrichtlinie" (Richtlinie 2008/115/EG des Europäischen Parlaments und des Rats vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger, ABl. L 348 vom 24. Dezember 2008 S. 98 ff; vgl. ANDRÉ EQUEY, Änderungen im Bereich der Zwangsmassnahmen im Ausländerrecht aufgrund der Übernahme der EG-Rückführungsrichtlinie durch die Schweiz, AJP 2011 S. 924 ff., dort S. 934): Diese geht grundsätzlich vom Vorrang der freiwilligen Ausreise aus (vgl. Art. 7 RL 2008/115/EG). Machen die Mitgliedstaaten - als "letztes Mittel" - von Zwangsmassnahmen zur Durchführung der Abschiebung von Widerstand leistenden Drittstaatsangehörigen Gebrauch, so müssen diese Massnahmen verhältnismässig sein und dürfen nicht über die Grenzen des Erforderlichen hinausgehen. Sie müssen nach dem einzelstaatlichen Recht im Einklang mit den Grundrechten und unter gebührender Berücksichtigung der Menschenwürde und körperlichen Unversehrtheit der betroffenen Personen erfolgen (Art. 8 Abs. 4 RL 2008/115/EG). Drittstaatsangehörige, gegen die ein Rückkehrverfahren hängig ist, können nur in Haft genommen werden, wenn im konkreten Fall keine anderen, milderen Zwangsmassnahmen wirksam erscheinen (vgl. EQUEY, a.a.O., S. 936); die Haftdauer hat so kurz wie möglich zu sein; sie darf sich nur auf die Dauer der laufenden Abschiebungsvorkehrungen erstrecken, soweit diese mit der gebotenen Sorgfalt vorangetrieben werden (vgl. Art. 15 Abs. 1 RL 2008/115/EG). Erweist sich, dass aus rechtlichen oder anderweitigen Erwägungen keine hinreichende Aussicht auf Abschiebung mehr besteht oder dass die Haftbedingungen nicht mehr gegeben sind, so ist die Haft nicht länger gerechtfertigt und die betroffene Person unverzüglich freizulassen (Art. 15 Abs. 4 RL 2008/115/EG). Als weniger intensive Massnahmen nennt die Richtlinie eine regelmässige Meldepflicht bei den Behörden, die Hinterlegung einer angemessenen Sicherheit, das Einreichen von Papieren und die Verpflichtung, sich an einem bestimmten Ort aufzuhalten (Art. 7 Abs. 3 RL 2008/115/EG; EQUEY, a.a.O., S. 936). In verfahrensrechtlicher Hinsicht sieht sie vor, dass die Rückkehrentscheidung eine sachliche und rechtliche Begründung sowie Informationen über mögliche Rechtsbehelfe enthalten muss und dem Betroffenen das Recht zu gewähren ist, gegen den entsprechenden Entscheid einen wirksamen Rechtsbehelf einlegen zu können (Art. 13 Abs. 1 RL 2008/115/EG).
3.2 Entgegen der Annahme des Haftrichters erscheint der Wegweisungsvollzug im vorliegenden Fall nicht hinreichend absehbar und hat die Ausschaffungshaft des Beschwerdeführers bei einer Auslegung von Art. 76 und Art. 80 AuG im Lichte der Vorgaben der Rückführungsrichtlinie und von Art. 5 Ziff. 1 lit. f EMRK als unverhältnismässig zu gelten:
3.2.1 Der Beschwerdeführer ist am 12. Juni 2012 aus dem Strafvollzug entlassen worden. Er hat sich wiederholt bereit erklärt, sich den Behörden für den Vollzug der Ausweisung, falls dieser flüchtlingsrechtlich zulässig sein sollte, bei seinen Eltern zur Verfügung zu halten. Entgegen der Einschätzung des Haftrichters bestehen trotz der früheren, schweren Straffälligkeit des Beschwerdeführers heute keine konkreten Anhaltspunkte dafür, dass er sich den Behörden für den Vollzug seiner Entfernungsmassnahme nach Beurteilung der Frage der flüchtlingsrechtlichen Vollziehbarkeit unter dem Gesichtswinkel des Non-Refoulement-Prinzips durch die zuständigen (Rechtsmittel-)Behörden zu gegebener Zeit nicht zur Verfügung halten wird: Der Beschwerdeführer wurde bereits am 13. August 2008 trotz der schweren Delikte, an denen er beteiligt war, durch die zuständige Kommission als nicht gemeingefährlich eingestuft. Der Therapieverlaufsbericht des Psychologischen Dienstes der Interkantonalen Strafanstalt Bostadel hielt am 25. Januar 2010 unter anderem fest, dass die Deliktsaufarbeitung mit dem Ziel der Risikoverminderung als abgeschlossen gelten könne. Aus dem Führungsbericht der Strafanstalt vom 14. Januar 2010 ergibt sich, dass sich der Beschwerdeführer während des sechsjährigen Aufenthalts stets tadellos verhalten und sich "äusserst einsichtig" gezeigt habe; er habe zum Ausdruck bringen können, dass er sein Fehlverhalten aufrichtig bedauere. In der Aussenwohngruppe - mit gelockertem Regime und regelmässigem Freigang - wurde er als "humorvoller, meist gut gelaunter Gefangener beschrieben, der sowohl den Angestellten wie auch den Mitgefangenen gegenüber ein korrektes, hilfsbereites und freundliches Auftreten" gezeigt habe. Sein Arbeitsmeister hebe seine exakte und saubere Arbeitsweise hervor; seine überdurchschnittliche Selbstdisziplin und Unermüdlichkeit seien manchmal kaum zu stoppen gewesen. Die Abteilung Straf- und Massnahmenvollzug ging in ihrer Verfügung vom 10. Mai 2012 dementsprechend davon aus, dass sich der Beschwerdeführer im Laufe der Therapie vom Delikt des Raubüberfalls distanziert, sein Verhalten als verwerflich betrachtet und die Verantwortung für seine Tat übernommen habe. Was das Risiko aktiver Tötungshandlungen betreffe, habe ein solches "in keinem Moment" bestanden. Es könne bei ihm nach wie vor weder von chronischer Gewalt- noch Tötungsbereitschaft ausgegangen werden; auch bestünden keine Anzeichen für die Annahme, dass er anderweitig weitere Verbrechen oder Vergehen begehen werde. Ob seine Wegweisung wird vollzogen werden können, sei noch unklar; auf jeden Fall könne davon ausgegangen werden, dass er in der Schweiz über einen sehr guten familiären Rückhalt verfüge, welcher ihm in der Zeit nach dem Freiheitsentzug zugutekommen werde.
3.2.2 Unter diesen Umständen ist nicht ersichtlich, weshalb die Ausschaffungshaft zur Sicherung des Vollzugs der Ausweisung aus dem Jahr 2007 erforderlich wäre und die beabsichtigte Sicherstellung nicht mit milderen Massnahmen (Ein- oder Ausgrenzung [Art. 74 AuG], Meldepflicht [Art. 64e AuG] usw.) ebenso wirksam, aber für den Betroffenen weniger einschneidend erreicht werden könnte. Soweit der Haftrichter auf die bisherige - bezüglich der Anordnung milderer Massnahmen relativ strenge - Praxis des Bundesgerichts verweist, verkennt er, dass die entsprechenden Urteile vor der Übernahme der RL 2008/115/EG und dem darin verankerten "Subsidiaritätsprinzip" ergangen sind, heute bei den Zwangsmassnahmen jedoch jeweils auch den entsprechenden europäischen Vorgaben Rechnung zu tragen ist (vgl. THOMAS HUGI YAR, Das Urteil El Dridi, die EU-Rückführungsrichtlinie und der Schengen-Besitzstand, in: Jusletter 11. Juli 2011, Rz. 15). Im Übrigen darf die Ausschaffungshaft - wie das Bundesgericht unlängst wieder festgestellt hat - nicht strafprozessualen oder ausschliesslich polizeilichen Sicherungszwecken dienen, sondern muss im Rahmen der Zweckgebundenheit der Festhaltung auf eine absehbare Ausschaffung ausgerichtet sein und hierfür erforderlich erscheinen (Urteil 2C_304/2012 vom 1. Mai 2012 E. 2.3.2; GÖKSÜ, a.a.O., N. 20 zu Art. 75 AuG; ZÜND, a.a.O., N. 10 zu Art. 75 AuG).
3.2.2 Unter diesen Umständen ist nicht ersichtlich, weshalb die Ausschaffungshaft zur Sicherung des Vollzugs der Ausweisung aus dem Jahr 2007 erforderlich wäre und die beabsichtigte Sicherstellung nicht mit milderen Massnahmen (Ein- oder Ausgrenzung [Art. 74 AuG], Meldepflicht [Art. 64e AuG] usw.) ebenso wirksam, aber für den Betroffenen weniger einschneidend erreicht werden könnte. Soweit der Haftrichter auf die bisherige - bezüglich der Anordnung milderer Massnahmen relativ strenge - Praxis des Bundesgerichts verweist, verkennt er, dass die entsprechenden Urteile vor der Übernahme der RL 2008/115/EG und dem darin verankerten "Subsidiaritätsprinzip" ergangen sind, heute bei den Zwangsmassnahmen jedoch jeweils auch den entsprechenden europäischen Vorgaben Rechnung zu tragen ist (vgl. THOMAS HUGI YAR, Das Urteil El Dridi, die EU-Rückführungsrichtlinie und der Schengen-Besitzstand, in: Jusletter 11. Juli 2011, Rz. 15). Im Übrigen darf die Ausschaffungshaft - wie das Bundesgericht unlängst wieder festgestellt hat - nicht strafprozessualen oder ausschliesslich polizeilichen Sicherungszwecken dienen, sondern muss im Rahmen der Zweckgebundenheit der Festhaltung auf eine absehbare Ausschaffung ausgerichtet sein und hierfür erforderlich erscheinen (Urteil 2C_304/2012 vom 1. Mai 2012 E. 2.3.2; GÖKSÜ, a.a.O., N. 20 zu Art. 75 AuG; ZÜND, a.a.O., N. 10 zu Art. 75 AuG).
3.3 3.3.1 Neben der Erforderlichkeit erscheint auch die Absehbarkeit des Vollzugs vorliegend unter dem Gesichtswinkel der Verhältnismässigkeit problematisch: Das Bundesamt für Migration hat dem Sicherheitsdepartement des Kantons Basel-Stadt am 24. Mai 2012 im Rahmen von dessen Anfrage um Vollzugsunterstützung mitgeteilt, dass im Ausweisungsentscheid keine Prüfung der flüchtlingsrechtlichen Fragen und einer allfälligen Verfolgungssituation erfolgt sei, weshalb die entsprechende Verfügung vom 15. August 2007 an einem "schwerwiegenden Mangel" leide. Zwar prüfte es - nach Rücksprache mit dem Kanton - in der Folge die entsprechenden Aspekte im Rahmen seines Amtsberichts vom 18. Juni 2012, doch erging zu keinem Zeitpunkt vor der Haftanordnung eine anfechtbare Widerrufsverfügung hinsichtlich des materiellen Status des Beschwerdeführers als Flüchtling im Sinne der Flüchtlingskonvention. Das Bundesamt erliess eine solche erst während des vorliegenden Verfahrens am 16. August 2012. Diese kann nunmehr innert 30 Tagen beim Bundesverwaltungsgericht angefochten werden; mit dessen Entscheid dürfte realistischerweise indessen kaum vor Ablauf der maximal möglichen Haftdauer von sechs Monaten (vgl. Art. 79 Abs. 1 AuG) zu rechnen sein. Zwar hat bereits der Haftrichter einlässlich geprüft, ob Weg- oder Vollzugshindernisse vorliegen, doch war er hierzu - wie dargelegt (vgl. E. 2.1) - unzuständig.
3.3.2 Eine zusätzliche Haftverlängerung bis zu 18 Monaten setzte voraus, dass die betroffene Person nicht mit der zuständigen Behörde kooperiert oder sich die Übermittlung der für die Ausreise erforderlichen Unterlagen durch einen Nicht-Schengen-Staat verzögert (Art. 79 Abs. 2 AuG). Da dem Betroffenen in Anwendung der Rückführungsrichtlinie die Möglichkeit eines wirksamen Rechtsbehelfs gegen die Rückkehrentscheidung einzuräumen ist (vgl. Art. 13 Abs. 1 RL 2008/115/EG), wozu auch deren flüchtlingsrechtliche Vollziehbarkeit unter dem Aspekt der Flüchtlingskonvention und der Grundrechte gehört, kann darin, dass er hiervon Gebrauch macht bzw. Gebrauch machen will, keine Verletzung der Mitwirkungspflichten gesehen werden, welche eine Verlängerung der ausländerrechtlichen Festhaltung über 6 Monate hinaus rechtfertigen könnte. Dies gilt hier umso mehr, als die Behörden während des Strafvollzugs hinreichend Gelegenheit gehabt hätten, die flüchtlingsrechtlichen Aspekte rechtzeitig zu prüfen und nötigenfalls der richterlichen Beurteilung zuzuführen, hiermit aber erst im Rahmen des Haftverfahrens begonnen haben und damit der gebotenen Sorgfalt bzw. den Geboten der Verfahrensbeschleunigung ungenügend nachgekommen sind. Wie das Bundesgericht bereits festgehalten hat, gilt das Beschleunigungsgebot auch während des Strafvollzugs und haben die Behörden die Ausschaffung zeitlich so vorzubereiten, dass möglichst keine zusätzliche ausländerrechtliche Haft zu deren Sicherung erforderlich wird (HUGI YAR, a.a.O., N. 10.99 ff.).
4. 4.1 Die vorliegende Beschwerde ist demnach gutzuheissen, die Haftgenehmigung aufzuheben und der Beschwerdeführer sofort aus der Ausschaffungshaft zu entlassen. Es steht den kantonalen Behörden frei, ihm Kontrollauflagen zu machen oder seine Aus- oder Eingrenzung auf ein bestimmtes Gebiet zu prüfen.
4.2 Dem Ausgang des Verfahrens entsprechend sind keine Kosten zu erheben (Art. 66 Abs. 4 BGG). Hingegen hat der Kanton Basel-Stadt den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Der Einzelrichter für Zwangsmassnahmen am Appellationsgericht des Kantons Basel-Stadt wird über die kantonale Kosten- und Entschädigungsfrage neu zu befinden haben (Art. 67 i.V.m. Art. 107 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Einzelrichters für Zwangsmassnahmen im Ausländerrecht am Appellationsgericht des Kantons Basel-Stadt vom 29. Juni 2012 wird aufgehoben. Der Beschwerdeführer ist mit sofortiger Wirkung aus der Haft zu entlassen.
2. 2.1 Es werden keine Kosten erhoben.
2.2 Der Kanton Basel-Stadt hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
2.3 Der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Appellationsgericht des Kantons Basel-Stadt hat über die kantonale Kosten- und Entschädigungsfrage neu zu befinden.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 28. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Hugi Yar