Sachverhalt:
A. X._ (geb. 1984) stammt aus Algerien. Das Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) trat am 10. März 2004 auf sein Asylgesuch nicht ein und forderte ihn auf, das Land umgehend zu verlassen, was er nicht tat. Am 6./7. November 2006 nahm das Migrationsamt des Kantons Zürich ihn in Ausschaffungshaft, welche der Haftrichter am Bezirksgericht Zürich bis zum 5. Februar 2007 genehmigte.
B. Am 30. Januar 2007 ordnete das Migrationsamt des Kantons Zürich gegen X._ die Durchsetzungshaft an, nachdem er sich am 7. Dezember 2006 geweigert hatte, das Flugzeug nach Algier zu besteigen. Die Haftrichterin prüfte diese am 1. Februar 2007 und bestätigte sie bis zum 28. Februar 2007. Hiergegen gelangte X._ am 9. Februar 2007 mit dem Antrag an das Bundesgericht, den haftrichterlichen Entscheid aufzuheben und ihn unverzüglich aus der Haft zu entlassen (Verfahren 2C_19/2007). Die Haftrichterin hat auf eine Vernehmlassung verzichtet. Das Migrationsamt des Kantons Zürich und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen. X._ hat am 13. März 2007 an seinen Anträgen und Ausführungen festgehalten.
C. Am 21. Februar 2007 ersuchte das Migrationsamt des Kantons Zürich das Bezirksgericht, die Durchsetzungshaft von X._ um zwei Monate zu verlängern, da er sich am 17. Februar 2007 erneut geweigert habe, den für ihn reservierten Rückflug nach Algier anzutreten, obwohl er erklärt habe, bereit zu sein, in seine Heimat zurückzukehren. Der Haftrichter bewilligte die Verlängerung am 28. Februar 2007 bis zum 30. April 2007. X._ gelangte am 5. März 2007 hiergegen wiederum mit dem Antrag an das Bundesgericht, den Entscheid des Haftrichters aufzuheben und ihn unverzüglich aus der Haft zu entlassen (Verfahren 2C_45/2007). Mit Blick auf das bereits hängige Verfahren wurde von weiteren Instruktionsmassnahmen abgesehen.

Das Bundesgericht zieht in Erwägung:
1. Die angefochtenen haftrichterlichen Entscheide ergingen nach dem Inkrafttreten des Bundesgesetzes vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG; SR 173.110, AS 2006 S. 1205 ff.). Die Eingaben sind somit als Beschwerden in öffentlich-rechtlichen Angelegenheiten entgegenzunehmen. Da sie sich auf denselben Beschwerdeführer beziehen und sich jeweils die gleichen Rechts- bzw. Sachverhaltsfragen stellen, können die Verfahren zusammengelegt und in einem gemeinsamen Urteil erledigt werden (<ref-law> in Verbindung mit <ref-law>; vgl. <ref-ruling> E. 1 S. 394).
2. 2.1 Hat ein Ausländer seine Pflicht zur Ausreise aus der Schweiz innerhalb der ihm angesetzten Frist nicht erfüllt und kann die rechtskräftige Weg- oder Ausweisung auf Grund seines persönlichen Verhaltens nicht vollzogen werden, so darf er, um der Ausreisepflicht Nachachtung zu verschaffen, in Durchsetzungshaft genommen werden, sofern die Anordnung der Ausschaffungshaft nicht zulässig ist oder keine andere, mildere Massnahme zum Ziel führt (Art. 13g Abs. 1 ANAG in der seit dem 1. Januar 2007 gültigen Fassung gemäss der Änderung des Asylgesetzes vom 16. Dezember 2005 [AS 2006 S. 4745 ff., dort S. 4767 und S. 4771]). Die Haft ist erstmals für einen Monat zulässig und kann hernach mit der Zustimmung der zuständigen kantonalen richterlichen Behörde (vgl. Art. 13g Abs. 3 ANAG) jeweils um zwei Monate verlängert werden, sofern der Ausländer weiterhin nicht bereit ist, sein Verhalten zu ändern und auszureisen. Die maximale Haftdauer beträgt grundsätzlich 18 Monate (Art. 13g Abs. 2 ANAG). Die Haft wird beendet, falls eine selbständige pflichtgemässe Ausreise nicht möglich ist, obwohl der Ausländer den behördlich vorgegebenen Mitwirkungspflichten nachkommt (Art. 13g Abs. 6 lit. a ANAG), oder die Schweiz weisungsgemäss verlassen (lit. b), die Ausschaffungshaft angeordnet (lit. c) oder einem Haftentlassungsgesuch entsprochen wird (lit. d). Die Vorbereitungs-, Ausschaffungs- und Durchsetzungshaft dürfen zusammen die maximale Haftdauer von 24 Monaten (bzw. bei Minderjährigen zwischen 15 und 18 Jahren von 12 Monaten) nicht überschreiten (Art. 13h ANAG in der Fassung vom 16. Dezember 2005).
2.2 Die Durchsetzungshaft findet ihre konventionsrechtliche Rechtfertigung vorab in Art. 5 Ziff. 1 lit. b (Haft zur Erzwingung einer durch das Gesetz vorgeschriebenen Verpflichtung) und nicht wie die Vorbereitungs- und Ausschaffungshaft ausschliesslich in Art. 5 Ziff. 1 lit. f EMRK (Haft zur Sicherung eines schwebenden Ausweisungsverfahrens; vgl. <ref-ruling> E. 4.2.3, 377 E. 3.1). Sie bezweckt, 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 der behördlichen Bemühungen - ohne ihre Kooperation nicht möglich ist (vgl. <ref-ruling> E. 4.2.3 S. 62 f.; AB 2005 S 375 ff. [Voten von Kommissionssprecherin Heberlein und Bundesrat Blocher]; AB 2005 N 1209 f. [Votum von Kommissionssprecher Müller Philipp]). Die Durchsetzungshaft soll das letzte Mittel darstellen, wenn und soweit keine andere Zwangsmassnahme zum Ziel führt, den illegal anwesenden Ausländer - auch gegen seinen Willen - in seine Heimat verbringen zu können (Urteil 2C_22/2007 vom 22. Februar 2007, E. 2.2.2). Wie alle staatlichen Massnahmen hat sie dem Verhältnismässigkeitsprinzip zu entsprechen; es ist jeweils im Einzelfall auf Grund der konkreten Umstände zu prüfen, ob sie geeignet bzw. erforderlich ist und nicht gegen das Übermassverbot, d.h. das sachgerechte und zumutbare Verhältnis von Mittel (Haft) und Zweck (Verhaltensänderung, damit die Ausschaffung vollzogen werden kann), verstösst (vgl. AB 2005 N 1209 [Votum von Kommissionssprecher Müller]; zur Ausschaffungshaft: Urteil des Bundesgerichts 2C_1/2007 vom 5. Februar 2007, E. 7 nicht publ. in <ref-ruling> ff.; <ref-ruling> ff.). Dabei ist im Rahmen von <ref-law> (gemäss Justizreform; früher <ref-law>) den Prämissen des Gesetzgebers Rechnung zu tragen, dass die Massnahme je nach den Umständen bis zu einer maximalen Haftdauer von 18 Monaten (bzw. bei Minderjährigen zwischen 15 und 18 Jahren von neun Monaten) als verhältnismässig gelten kann und der Betroffene es im Übrigen in der Hand hat, die Haft jederzeit zu beenden, indem er seiner Ausreisepflicht nachkommt. Art. 13g ANAG ist im Rahmen dieser Vorgaben verfassungs- und konventionskonform auszulegen (kritisch zur Durchsetzungshaft: Jürg Schertenleib, Die Teilrevision des Asylgesetzes, Kommentierte Übersicht, Bern 2006, S. 19).
3. Die gegen den Beschwerdeführer angeordnete und in der Folge verlängerte Durchsetzungshaft genügt diesen Anforderungen:
3.1 Die Neuregelung der Zwangsmassnahmen im Ausländerrecht im Anhang zur Änderung des Asylgesetzes vom 16. Dezember 2005 gilt, soweit sie am 1. Januar 2007 in Kraft getreten ist, auch für Ausländer, deren Wegweisungsverfahren zu diesem Zeitpunkt noch hängig waren, wobei eine unter dem bisherigen Recht bereits ausgestandene Administrativhaft jedoch grundsätzlich auf die neue Maximaldauer anzurechnen ist (<ref-ruling> E. 4 und 5). Der Beschwerdeführer befand sich vom 6. November 2006 bis zum 1. Februar 2007 in Ausschaffungshaft, bevor er auf diesen Zeitpunkt hin in Durchsetzungshaft genommen wurde. Die zulässige maximale Gesamtdauer der Zwangsmassnahmen von 24 Monaten (Art. 13h ANAG) ist damit bei Weitem noch nicht erreicht, weshalb sich zusätzliche Ausführungen in diesem Zusammenhang erübrigen.
3.2 Das Bundesamt für Flüchtlinge ist am 10. März 2004 auf das Asylgesuch des Beschwerdeführers nicht eingetreten und hat ihn weggewiesen; der entsprechende Entscheid ist unangefochten in Rechtskraft erwachsen. Der Beschwerdeführer kam der Aufforderung, das Land sofort zu verlassen, nicht nach; er tauchte hier vielmehr bei Kollegen in Genf unter, nachdem seine Staatsbürgerschaft von den algerischen Behörden am 16. September 2004 anerkannt und die Ausstellung eines Laissez-passer-Papiers für seine Rückreise in Aussicht gestellt worden war. Am 9. November 2006 erklärte er dem Haftrichter gegenüber, dass er nicht nach Algerien ausgeschafft werden wolle, sondern in der Schweiz eine Chance erhalten und hier allenfalls arbeiten oder heiraten möchte. Der Beschwerdeführer weigerte sich dementsprechend am 7. Dezember 2006 und hernach am 17. Februar 2007 erneut, freiwillig nach Algerien zurückzukehren, obwohl er bei der richterlichen Einvernahme vom 1. Februar 2007 im Beisein seiner Anwältin noch erklärt hatte, nunmehr bereit zu sein, in seine Heimat zurückzureisen.
3.3 Da mit Algerien kein Abkommen über Sonderflüge für Personen besteht, die nur zwangsweise ausgeschafft werden können, kann der Beschwerdeführer bloss dorthin zurückgeführt werden, wenn er bereit ist, hierbei zu kooperieren, was er - um eine Haftentlassung zu erwirken - zwar in Aussicht gestellt, indessen nicht getan hat. Eine (weitere) Ausschaffungshaft erscheint zurzeit nicht möglich, da diese voraussetzen würde, dass sich der zwangsweise Vollzug der Wegweisung auch tatsächlich gegen seinen Willen in absehbarer Zeit realisieren liesse (vgl. <ref-ruling> E. 4.2.3). Dies könnte künftig allenfalls wieder in Betracht fallen, sollten die vom Bundesamt für Migration in seiner Vernehmlassung in Aussicht gestellten Verhandlungen mit den algerischen Behörden konkrete Resultate zeitigen.
4. Was der Beschwerdeführer gegen die Haftgenehmigungen weiter einwendet, überzeugt nicht:
4.1 Soweit er geltend macht, beim Entscheid über die Durchsetzungshaft dürfe sein Verhalten vor dem 1. Januar 2007 nicht berücksichtigt werden, da dies einer unzulässigen Rückwirkung gleichkomme, übersieht er, dass keine solche vorliegt, wenn der Gesetzgeber - wie hier - auf Verhältnisse abstellt, die zwar unter der Herrschaft des alten Rechts entstanden sind, beim Inkrafttreten des neuen jedoch fortdauern. Es ist verfassungsrechtlich nicht verboten, für zeitlich offene Dauersachverhalte in Zukunft andere Rechtsfolgen vorzusehen, sofern dem nicht wohlerworbene Rechte bzw. der Grundsatz des Vertrauensschutzes entgegenstehen (<ref-law>), was hier nicht der Fall ist (vgl. <ref-ruling> E. 4.3; <ref-ruling> E. 4a S. 135; <ref-ruling> E. 3b/dd S. 124; <ref-ruling> E. 3b S. 258; Häfelin/Müller/Uhlmann, Allgemeines Verwaltungsrecht, 5. Aufl., Zürich 2006, Rz. 342). Der Gesetzgeber hat im Zusammenhang mit der Einführung der verschärften Zwangsmassnahmen keine ausdrückliche, hiervon abweichende Regelung getroffen. Nach Art. 2 der Schlussbestimmungen zum Bundesgesetz vom 18. März 1994 über Zwangsmassnahmen im Ausländerrecht (AS 1995 S. 146 ff.) galt zwar für die im Zeitpunkt des Inkrafttretens des damaligen Gesetzes hängigen Verfahren - wie dies gemäss Abs. 1 der Übergangsbestimmungen zur Änderung des Asylgesetzes vom 16. Dezember 2005 (AS 2006 S. 4762) auch heute der Fall ist - das neue Recht, doch war die Anordnung einer Vorbereitungs- oder Ausschaffungshaft damals nur aufgrund von Tatsachen möglich, die nach Inkrafttreten des Gesetzes eingetreten waren; auf eine analoge Regelung hat der Gesetzgeber bei der Teilrevision des Asylgesetzes und der Einführung der Durchsetzungshaft indessen verzichtet. Das Bundesgericht hat es im Übrigen bereits in seiner Rechtsprechung zu Art. 2 der Schlussbestimmungen des Zwangsmassnahmengesetzes als zulässig erachtet, dass nach dem 1. Februar 1995 eingetretene haftbegründende Tatsachen im Lichte des früheren Verhaltens des Betroffenen gewürdigt werden (<ref-ruling> E. 2a S. 151 mit Hinweisen).
4.1 Soweit er geltend macht, beim Entscheid über die Durchsetzungshaft dürfe sein Verhalten vor dem 1. Januar 2007 nicht berücksichtigt werden, da dies einer unzulässigen Rückwirkung gleichkomme, übersieht er, dass keine solche vorliegt, wenn der Gesetzgeber - wie hier - auf Verhältnisse abstellt, die zwar unter der Herrschaft des alten Rechts entstanden sind, beim Inkrafttreten des neuen jedoch fortdauern. Es ist verfassungsrechtlich nicht verboten, für zeitlich offene Dauersachverhalte in Zukunft andere Rechtsfolgen vorzusehen, sofern dem nicht wohlerworbene Rechte bzw. der Grundsatz des Vertrauensschutzes entgegenstehen (<ref-law>), was hier nicht der Fall ist (vgl. <ref-ruling> E. 4.3; <ref-ruling> E. 4a S. 135; <ref-ruling> E. 3b/dd S. 124; <ref-ruling> E. 3b S. 258; Häfelin/Müller/Uhlmann, Allgemeines Verwaltungsrecht, 5. Aufl., Zürich 2006, Rz. 342). Der Gesetzgeber hat im Zusammenhang mit der Einführung der verschärften Zwangsmassnahmen keine ausdrückliche, hiervon abweichende Regelung getroffen. Nach Art. 2 der Schlussbestimmungen zum Bundesgesetz vom 18. März 1994 über Zwangsmassnahmen im Ausländerrecht (AS 1995 S. 146 ff.) galt zwar für die im Zeitpunkt des Inkrafttretens des damaligen Gesetzes hängigen Verfahren - wie dies gemäss Abs. 1 der Übergangsbestimmungen zur Änderung des Asylgesetzes vom 16. Dezember 2005 (AS 2006 S. 4762) auch heute der Fall ist - das neue Recht, doch war die Anordnung einer Vorbereitungs- oder Ausschaffungshaft damals nur aufgrund von Tatsachen möglich, die nach Inkrafttreten des Gesetzes eingetreten waren; auf eine analoge Regelung hat der Gesetzgeber bei der Teilrevision des Asylgesetzes und der Einführung der Durchsetzungshaft indessen verzichtet. Das Bundesgericht hat es im Übrigen bereits in seiner Rechtsprechung zu Art. 2 der Schlussbestimmungen des Zwangsmassnahmengesetzes als zulässig erachtet, dass nach dem 1. Februar 1995 eingetretene haftbegründende Tatsachen im Lichte des früheren Verhaltens des Betroffenen gewürdigt werden (<ref-ruling> E. 2a S. 151 mit Hinweisen).
4.2 4.2.1 Das Gleiche gilt hier: Der Beschwerdeführer ist am 16. Januar 2007 und damit nach Einführung der Durchsetzungshaft zu den Gründen befragt worden, aus denen er sich geweigert hat, am 7. Dezember 2006 das Flugzeug nach Algerien zu besteigen. Er erklärte dabei, nicht heimreisen, sondern weiterhin in der Schweiz - jedoch nicht im Gefängnis - bleiben zu wollen; würde er aus der Haft entlassen, ginge er nach Italien. Damit hat er sich erneut in unzweideutiger Weise geweigert, in seine Heimat zurückzukehren, was dafür spricht, dass er nach wie vor versucht, den Vollzug seiner Wegweisung zu vereiteln (vgl. Art. 13b Abs. 1 lit. c ANAG: "Untertauchensgefahr"; <ref-ruling> E. 3.1 S. 59 f; <ref-ruling> E. 2.1 S. 243; <ref-ruling> E. 3b/aa S. 375). Er war am 17. Februar 2007 denn auch wiederum nicht bereit, nach Algier zurückzukehren, was er diesmal damit rechtfertigte, es sich "anders überlegt" zu haben, da Algerien "nicht gut" für ihn sei; er habe eine Anwältin getroffen, die ihm gesagt habe, dass eine Chance bestehe, dass er entlassen werde und sich dann selbständig nach Frankreich oder Italien absetzen könne.
4.2.2 Soweit der Beschwerdeführer geltend macht, Art. 13g ANAG diene nach seinem Wortlaut nur dazu, "der Ausreisepflicht Nachachtung zu verschaffen" und nicht die Rückkehr in den Heimatstaat sicherzustellen, verkennt er, dass mit der entsprechenden Pflicht nur eine Ausreise gemeint sein kann, die mit einer rechtmässigen Einreise in ein anderes Land verbunden ist: Die Schweiz darf zwischenstaatlich nicht bewusst zu einer illegalen Einreise in einen Drittstaat Hand bieten; dies ergibt sich ohne Weiteres aus den mit den Nachbarstaaten unterzeichneten Rückübernahmeabkommen, welche die Schweiz regelmässig "im Bestreben, gegen die illegale Einwanderung vorzugehen," dazu verpflichten, widerrechtlich von ihrem Territorium in diese Staaten einreisende (Dritt-)Ausländer zurückzunehmen (vgl. etwa das Abkommen vom 10. September 1998 zwischen der Schweizerischen Eidgenossenschaft und der Italienischen Republik über die Rückübernahme von Personen mit unbefugtem Aufenthalt [SR 0.142.114.549] oder vom 28. Oktober 1998 zwischen dem Schweizerischen Bundesrat und der Regierung der Französischen Republik über die Rückübernahme von Personen mit unbefugtem Aufenthalt [SR 0.142.113.499]). Die Erfüllung der Zusage, illegal (d.h. ohne Papiere und Visum) in einen Drittstaat einzureisen, wäre im Übrigen durch die schweizerischen Behörden naturgemäss auch kaum überprüfbar; der Betroffene könnte sich damit begnügen, hier bloss wieder unterzutauchen. Da der Beschwerdeführer nur über einen Laissez-passer verfügt, der ihm erlaubt, in seinen Heimatstaat zurückzureisen, und er nicht geltend macht, sich rechtmässig in einen Drittstaat - insbesondere nach Italien - begeben zu können, lässt nur seine Heimkehr nach Algerien die Durchsetzungshaft dahinfallen. Wie der Haftrichter in seinem Entscheid vom 28. Februar 2007 zu Recht ausgeführt hat, kann die Zulässigkeit der Durchsetzungshaft nicht von allfälligen Wünschen oder Präferenzen des Betroffenen in Bezug auf seine Destination oder von seiner Bereitschaft abhängen, sich allenfalls illegal in einen Drittstaat zu begeben. Einzig der Heimatstaat ist verpflichtet, seine Staatsbürger wieder zurückzunehmen (<ref-ruling> E. 4.1.2 S. 60; Ignaz Seidl-Hohenveldern, Völkerrecht, 9. Aufl., Köln/Berlin/Bonn/München 1997, Rz. 1641; Stein/von Buttlar, Völkerrecht, 11. Aufl., Köln/Berlin/München 2005, Rz. 576 und 583).
4.2.3 Entgegen der Kritik des Beschwerdeführers umschreibt Art. 13g ANAG die ihm auferlegte Pflicht, zu deren Durchsetzung er in Haft genommen wurde, hinreichend spezifisch und konkret im Sinne der Rechtsprechung zu Art. 5 Ziff. 1 lit. b EMRK; die Haft erweist sich - zumindest zurzeit - auch ohne Weiteres noch als verhältnismässig (vgl. <ref-ruling> E. 4.2.3 mit Hinweisen; zu Art. 5 Ziff. 1 lit. b EMRK: Christoph Grabenwarter, Europäische Menschenrechtskonvention, 2. Aufl., München/Wien 2005, Rz. 13 f. und Rz. 25 von § 21; Mark E. Villiger, Handbuch der Europäischen Menschenrechtskonvention, Zürich 1999, Rz. 333 f. und Rz. 339 ff.). Ein unzulässiger Eingriff in das verfassungsmässige Recht auf persönliche Freiheit (<ref-law>; vgl. <ref-ruling> E. 3.1, 58 E. 6.1 und 6.3) liegt nicht vor, nachdem sämtliche Voraussetzungen von <ref-law> erfüllt sind: Die Inhaftierung des Beschwerdeführers beruht auf einer klaren gesetzlichen Grundlage, liegt zur Durchsetzung des Vollzugs seiner rechtskräftigen Wegweisung im öffentlichen Interesse und erweist sich hierzu als geeignet und wegen seines renitenten bzw. widersprüchlichen Verhaltens als erforderlich.
5. 5.1 Die Beschwerden sind unbegründet, soweit das Verfahren 2C_19/2007 im Hinblick auf den Zeitablauf und auf ein damit allenfalls verbundenes Dahinfallen des aktuellen praktischen Interesses nicht gegenstandslos geworden ist (<ref-law>; vgl. Seiler, in: Seiler/von Werdt/Güngerich [Hrsg.], Bundesgerichtsgesetz, Bern 2007, Rz. 33 zu Art. 89); sie sind in diesem Sinne abzuweisen.
5.2 Der Beschwerdeführer beantragt für diesen Fall, ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren; dem Ersuchen kann nicht entsprochen werden, da seine Eingaben zum Vornherein aussichtslos waren (vgl. Art. 64 Abs. 1 und 2 BGG): Erschien die Gewährung der unentgeltlichen Verbeiständung in den kantonalen Verfahren noch als geboten, rechtfertigt sie sich vor Bundesgericht nicht mehr, nachdem die Verlustchancen aufgrund der zutreffenden Ausführungen in den angefochtenen Entscheiden wesentlich grösser waren als die Aussichten auf einen Erfolg (vgl. Seiler, in: Seiler/von Werdt/Güngerich [Hrsg.], Bundesgerichtsgesetz, Bern 2007, Rz. 21 und 23 zu Art. 64). Es kann jedoch davon abgesehen werden, eine Gerichtsgebühr zu erheben (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Verfahren 2C_19/2007 und 2C_45/2007 werden vereinigt.
2. Die Beschwerde 2C_19/2007 wird abgewiesen, soweit sie nicht gegenstandslos geworden ist.
3. Die Beschwerde 2C_45/2007 wird abgewiesen.
4. Die Gesuche um unentgeltliche Rechtspflege und Verbeiständung werden abgewiesen.
5. Es werden keine Kosten erhoben.
6. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt des Kantons Zürich und dem Bezirksgericht Zürich, Haftrichter, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 2. April 2007
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: