Sachverhalt:
A. Der libanesische Staatsangehörige X._ (geb. 1970) reiste illegal in die Schweiz ein und ersuchte im Jahre 2006 bzw. 2007 um Asyl. Er wurde dem Kanton Zürich zugeteilt. Das Bundesamt für Migration lehnte sein Asylgesuch am 28. November 2007 ab. Die dagegen erhobene Beschwerde wurde vom Bundesverwaltungsgericht am 31. Oktober 2008 abgewiesen. Zwischenzeitlich - am 2. Mai 2008 - ehelichte X._ die im Kanton Graubünden wohnhafte deutsche Staatsangehörige A._ (geb. 1957). Zwei Wochen später stellte die Ehefrau einen Antrag auf Familiennachzug für X._. Mit elektronischer Post vom 24. November 2008 teilte das Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden dem Rechtsvertreter von X._ mit, es werde auf das Nachzugsgesuch erst eintreten, wenn dieser das Land verlassen habe.
Das Migrationsamt des Kantons Zürich nahm X._ am 16. Dezember 2008 in Ausschaffungshaft. Diese wurde vom Haftrichter am Bezirksgericht Zürich mit Verfügung vom 18. Dezember 2008 bis zum 15. März 2009 bewilligt.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt X._ dem Bundesgericht, die Verfügung des Bezirksgerichts aufzuheben und ihn sofort aus der Ausschaffungshaft zu entlassen.
Das Migrationsamt des Kantons Zürich stellt den Antrag, die Beschwerde abzuweisen. Das Bezirksgericht sowie das Bundesamt für Migration haben keine Vernehmlassung eingereicht bzw. auf eine solche verzichtet. X._ hat sich am 6. Februar 2009 ergänzend geäussert.

Erwägungen:
1. Das Bundesgericht prüft seine Zuständigkeit und die Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (<ref-law>; <ref-ruling> E. 1 Ingress S. 140 mit Hinweisen). Die Beschwerde wurde beim Bundesgericht erst im Jahre 2009 eingereicht. Nach <ref-law> setzen die Kantone als unmittelbare Vorinstanzen des Bundesgerichts obere Gerichte ein, soweit nicht nach einem anderen Bundesgesetz Entscheide anderer richterlicher Behörden der Beschwerde an das Bundesgericht unterliegen. Die diesbezügliche Anpassungsfrist nach <ref-law> ist seit dem 1. Januar 2009 abgelaufen. Es ist fraglich, ob das Bezirksgericht ein oberes Gericht darstellt; auch sieht kein anderes Bundesgesetz vor, dass im Bereich der Ausschaffungshaft untere richterliche Behörden unmittelbare Vorinstanzen des Bundesgerichts sein können (vgl. Urteil 2C_10/2009 und 2C_25/2009 vom 5. Februar 2009 E. 3-5). Der Haftrichter erliess seine Verfügung jedoch noch im Jahre 2008, mithin vor Ablauf der erwähnten Anpassungsfrist. Entsprechend <ref-law> ist auf den Zeitpunkt des Ergehens des angefochtenen Entscheids abzustellen und nicht auf einen späteren Zeitpunkt wie etwa den der Erhebung der Beschwerde an das Bundesgericht. Deshalb bedarf es hier noch keines oberen Gerichts als unmittelbare Vorinstanz des Bundesgerichts. Die frist- und formgerecht erhobene Beschwerde ist daher an die Hand zu nehmen.
2. Der Beschwerdeführer macht geltend, die Vorinstanzen hätten zu Unrecht eine Untertauchensgefahr angenommen. Auch sei die Haft unverhältnismässig, da er mit einer in der Schweiz ansässigen deutschen Staatsangehörigen verheiratet sei und diese einen Anspruch habe, ihren Ehegatten nachzuziehen.
3. Der Haftrichter beruft sich auf den Haftgrund des Art. 76 Abs. 1 lit. b Ziff. 4 AuG (SR 142.20). Demnach kann ein Ausländer in Ausschaffungshaft genommen werden, wenn ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet wurde und sein bisheriges Verhalten darauf schliessen lässt, dass er sich behördlichen Anordnungen widersetzt. Unbeachtet des Vorliegens eines Haftgrundes ist eine Haft zu beenden, wenn sich erweist, dass der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar ist (vgl. Art. 80 Abs. 6 lit. a AuG). Die Behörden haben die für den Vollzug der Weg- und Ausweisung notwendigen Vorkehren umgehend zu treffen (Art. 76 Abs. 4 AuG; sog. Beschleunigungsgebot). Schliesslich soll die Haft als Ganzes verhältnismässig sein (vgl. <ref-ruling> E. 1 S. 58; Näheres bei Thomas Hugi Yar, Zwangsmassnahmen im Ausländerrecht, in: Uebersax et al., Ausländerrecht, 2. Aufl. 2009, Rz. 10.114 ff., S. 478 ff.).
4. Das Bundesgericht wendet das Recht gemäss <ref-law> - unter Vorbehalt von dessen Abs. 2 - von Amtes wegen an. Es ist weder an die in der Beschwerde vorgetragene Begründung der Rechtsbegehren noch an die Erwägungen der Vorinstanz gebunden. Es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen oder aus einem anderen als dem angerufenen Grund gutheissen (<ref-ruling> E. 1.2 S. 152).
5. Die Behörden haben das Beschleunigungsgebot bisher beachtet. Sie hatten auf Ende des Jahres 2008 einen Rückflug des Beschwerdeführers in seine Heimat organisiert. Dieser weigerte sich jedoch, das Flugzeug zu besteigen.
6. Problematisch könnte sich die Haft mit Blick auf die mit einer deutschen Staatsangehörigen am 2. Mai 2008 geschlossene Ehe erweisen. Seiner Ehefrau, die am 1. Juli 2006 in die Schweiz eingereist ist, wurde eine bis zum 3. Juni 2012 gültige Aufenthaltsbewilligung EG/EFTA erteilt.
6.1 Wohl liegt ein den Beschwerdeführer zur Ausreise verpflichtender Entscheid vor: Am 28. November 2007 lehnte das Bundesamt für Migration ein vom Beschwerdeführer eingereichtes Asylgesuch ab und verfügte seine Wegweisung aus der Schweiz. Die hiegegen erhobene Beschwerde wies das Bundesverwaltungsgericht am 31. Oktober 2008 ab. Einer ihm bis zum 20. November 2008 angesetzten Ausreisefrist kam der Beschwerdeführer nicht nach. Die erwähnten Behörden liessen jedoch die Eheschliessung vom 2. Mai 2008 unberücksichtigt, sei es, weil diese im Zeitpunkt ihres Entscheides noch gar nicht stattgefunden hatte bzw. weil dieser Umstand nicht den Verfahrensgegenstand bildete.
6.2 Die Frage der Rechtmässigkeit bzw. Verbindlichkeit der Weg- oder Ausweisung kann der Haftrichter nur in eng begrenztem Rahmen aufwerfen. Er darf die Massgeblichkeit von Wegweisungsentscheiden allein im Hinblick auf die Rechtmässigkeit der Ausschaffungshaft und dabei höchstens dann unmittelbar in Frage stellen, wenn sie augenfällig unzulässig bzw. derart offensichtlich falsch sind, dass sie sich letztlich als nichtig erweisen (<ref-ruling> E. 2.2.2 S. 197 f. mit Hinweisen). Auch unter dem Gesichtspunkt von Art. 80 Abs. 6 lit. a AuG lässt sich die Vollziehbarkeit eines entsprechenden Entscheides nicht leichthin verneinen. Die Möglichkeit, dass der Ausländer nach Eröffnung des Wegweisungsentscheids einen Anspruch auf eine ausländerrechtliche Bewilligung oder ein sonstwie geartetes Recht zum Verbleiben in der Schweiz erworben haben könnte, lässt die Vollziehbarkeit des Wegweisungsentscheids und damit die Grundlage der Ausschaffungshaft nicht schon dahinfallen. In der Regel ist dies zum Vornherein kaum anzunehmen, solange kein Bewilligungsverfahren bei der zuständigen Behörde anhängig gemacht worden ist, und auch nach Einleitung eines solchen Verfahrens wird der Haftrichter die Haftgenehmigung höchstens dann gestützt auf Art. 80 Abs. 6 lit. a AuG verweigern können, wenn eine gewisse Wahrscheinlichkeit dafür besteht, dass die Anwesenheit des Ausländers im Land aus rechtlichen Gründen für einige Zeit geduldet werden muss (vgl. Urteil 2P.198/2002 vom 3. Oktober 2002 E. 3.1). Das könnte mit Blick auf die immerhin nach Art. 8 EMRK und Art. 13 und 14 BV geschützte Ehe zutreffen.
6.3 Einer diesbezüglichen Prüfung bzw. Duldung steht <ref-law> (SR 142.31) nicht entgegen. Zwar kann ein Ausländer gemäss dieser Bestimmung ab Einreichung seines Asylgesuchs bis zur Ausreise nach einer rechtskräftig angeordneten Wegweisung kein Verfahren um Erteilung einer Aufenthaltsbewilligung einleiten. Das gilt seinem Wortlaut zufolge indes nicht, wenn ein Anspruch auf Erteilung einer Bewilligung besteht, was nachfolgend aufzuzeigen ist (vgl. E. 6.4 und 6.5). Einer Anerkennung eines Rechtsanspruchs auf Aufenthaltsbewilligung für den ausländischen Gatten steht eine gegen den Ausländer verhängte Einreisesperre als solche ebenso wenig entgegen (vgl. Urteil 2C_473/2008 vom 17. November 2008 E. 2.3). Daher spielt hier auch keine Rolle, dass der Beschwerdeführer im Jahre 1995 mit einem Einreiseverbot in die Schweiz auf unbestimmte Zeit belegt worden war. Gemäss einer Mitteilung des Bundesamtes für Migration vom 22. Januar 2009 wurde das erwähnte Verbot im Übrigen am 7. November 2007 wieder aufgehoben.
6.4 Der Beschwerdeführer könnte als Ehepartner einer gestützt auf das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) in der Schweiz anwesenheitsberechtigten Person einen (abgeleiteten) Aufenthaltsanspruch aus Art. 3 Anhang I FZA haben. Das Aufenthaltsrecht nach diesem Abkommen entsteht nicht erst durch Erteilung einer Bewilligung, sondern bereits aufgrund der Erfüllung der Bewilligungsvoraussetzungen; eine Person, die gestützt auf das Abkommen an sich aufenthaltsberechtigt wäre, darf sich selbst dann zunächst in der Schweiz aufhalten, wenn die Behörden prüfen, ob der erstmaligen Erteilung der Aufenthaltserlaubnis Gründe der öffentlichen Ordnung oder Sicherheit entgegen stehen (vgl. <ref-ruling> E. 4 S. 58 f.; Urteil 2A.494/2003 vom 24. August 2004 E. 4.3; Art. 5 Anhang I FZA in Verbindung mit Art. 3 Abs. 3 und Art. 5 Abs. 1 der Richtlinie 64/221/EWG vom 25. Februar 1964 [ABl. Nr. 56, 1964, S. 850]). Art. 17 AuG, der grundsätzlich ein Abwarten des Verfahrens im Ausland verlangt, spielt in diesem Zusammenhang keine Rolle.
Nach der bisherigen Praxis muss sich der Beschwerdeführer als sog. Drittstaatsangehöriger - in casu Libanese - allerdings bereits rechtmässig mit einem nicht nur vorübergehenden Aufenthaltstitel in der Schweiz oder einem anderen Vertragsstaat aufgehalten haben, damit aus Art. 3 Anhang I FZA ein Aufenthaltsrecht abgleitet werden kann (vgl. <ref-ruling> E. 3.6 S. 9 ff., unlängst bestätigt in <ref-ruling> E. 3 S. 14 ff.). Das ist und war beim Beschwerdeführer nicht der Fall. Zwar durfte er den Ausgang seines hängigen Asylverfahrens in der Schweiz abwarten. Das verschaffte ihm jedoch keinen nicht nur vorübergehenden Aufenthaltstitel im Sinne der erwähnten Praxis. Diese geht auf ein Urteil des Gerichtshofs der Europäischen Gemeinschaften (EuGH) vom 23. September 2003 zurück (C-109/01 Akrich Slg. 2003 I-9607). Wohl hat sich der EuGH in einem Urteil vom 25. Juli 2008 (C-127/08 Metock et al., insbes. Randnrn. 58 ff.) von seinen Ausführungen im Urteil Akrich inzwischen distanziert. Was das für Auswirkungen auf das Freizügigkeitsabkommen haben wird, ist für die kantonalen Instanzen aber noch nicht absehbar, weshalb im haftrechtlichen Verfahren nicht davon ausgegangen werden kann, die Wegweisung bzw. deren Vollzug seien mit Blick auf dieses Abkommen augenfällig unzulässig (vgl. auch Urteil 2C_587/2008 vom 4. Dezember 2008 E. 2.1 und Rundschreiben des Bundesamts für Migration vom 20. Oktober 2008 zum erwähnten Urteil Metock).
6.5 Einen grundsätzlichen Anspruch auf Bewilligung des Aufenthalts im Wege des Familiennachzugs kann der Beschwerdeführer bzw. seine Ehefrau - wie eine Schweizerin - jedoch aus Art. 42 Abs. 1 AuG, welcher hier mit Blick auf das Diskriminierungsverbot des Art. 2 FZA gilt, ableiten (vgl. <ref-ruling> E. 3.6 S. 21 f.). Allerdings haben gemäss Art. 17 Abs. 1 AuG auch Ausländer, die für einen vorübergehenden Aufenthalt rechtmässig eingereist sind und die nachträglich eine Bewilligung für einen dauerhaften Aufenthalt beantragen, den Entscheid im Ausland abzuwarten. Werden die Zulassungsvoraussetzungen offensichtlich erfüllt, so kann die zuständige kantonale Behörde den Aufenthalt während des Verfahrens gestatten (Art. 17 Abs. 2 AuG; vgl. auch Urteil 2D_98/2008 vom 12. Dezember 2008 E. 4 und 5 ).
Es fragt sich, ob die Zulassungsvoraussetzungen vorliegend offensichtlich erfüllt sind. Wie ausgeführt, lehnt das Amt für Polizeiwesen und Zivilrecht Graubünden als Fremdenpolizei es ab, auf das Nachzugsgesuch einzutreten, solange sich der Beschwerdeführer in der Schweiz aufhält. Damit verweigert sie inzident, den Aufenthalt gemäss Art. 17 Abs. 2 AuG vorübergehend zu gestatten. Der Beschwerdeführer hat nicht dargetan und es ist aus den Akten auch nicht ersichtlich, dass er vor Erlass der haftrichterlichen Verfügung eine Änderung des Entscheids der Bündner Fremdenpolizei erwirkt hätte. Dass der Entscheid der letztgenannten Behörde augenfällig unzulässig wäre, kann nicht gesagt werden. Vorliegend bestehen mehrere Anzeichen für eine Scheinehe, namentlich: Enger zeitlicher Zusammenhang zwischen der Abweisung des Asylgesuchs und der Eheschliessung; mehrfache Versuche des Beschwerdeführers, in die Schweiz oder andere europäische Länder illegal einzureisen und sich dort aufzuhalten (in der Schweiz bereits zwischen 1993 und 1996); unterschiedliche Kulturkreise und erheblicher Altersunterschied der Eheleute. Aus den Akten ergeben sich zudem Hinweise, dass der Beschwerdeführer in Deutschland in nicht unerheblicher Weise straffällig geworden ist. Die Bündner Fremdenpolizei forderte den Beschwerdeführer im September 2008 denn auch zur Vorlage eines deutschen Strafregisterauszuges auf. Der Beschwerdeführer hat nicht dargetan, dass er dem nachgekommen wäre und der Verdacht der Behörden unbegründet sei. Demnach kann nicht davon ausgegangen werden, dass die Zulassungsvoraussetzungen im Sinne von Art. 17 Abs. 2 AuG offensichtlich erfüllt sind (vgl. auch Art. 51 und 62 f. AuG) bzw. dass der Entscheid der Bündner Fremdenpolizei, den Aufenthalt während des Bewilligungsverfahrens nicht zu gestatten, augenfällig unzulässig ist. Dabei kann offen gelassen werden, inwieweit Art. 17 Abs. 2 AuG überhaupt auf illegal eingereiste Asylbewerber anwendbar ist
6.6 Nach dem Gesagten durfte der Haftrichter davon ausgehen, dass ein den Beschwerdeführer zur Ausreise verpflichtender Entscheid vorliegt, dem derzeit weder eine Duldung des Aufenthaltes nach dem Freizügigkeitsabkommen noch nach Art. 17 Abs. 2 AuG entgegensteht.
7. Gegen den von den Vorinstanzen angenommenen Haftgrund der Untertauchensgefahr im Sinne von Art. 76 Abs. 1 lit. b Ziff. 4 AuG macht der Beschwerdeführer geltend, er habe der Aufforderung der Bündner Fremdenpolizei, den Kanton Graubünden zu verlassen und in den Kanton Zürich zurückzukehren, Folge geleistet.
Dem Beschwerdeführer ist insoweit Recht zu geben, als ihm - entgegen den Ausführungen der Vorinstanz - angesichts der Aufforderung der Bündner Fremdenpolizei in einem Schreiben vom 26. September 2008 nicht vorgehalten werden kann, er habe sich nicht am Wohnort seiner Ehefrau bereit gehalten. Der Beschwerdeführer lässt jedoch unerwähnt, dass er sich anderen behördlichen Anordnungen widersetzt hatte. Wie die Vorinstanz richtig bemerkt, gelangte er trotz Einreisesperre erneut in die Schweiz. Aufforderungen zur Ausreise hat er nicht befolgt. Schon im Jahre 1996 hatte er aufgrund illegalen Aufenthaltes ausgeschafft werden müssen. Er ist zudem bereits unter einer falschen Identität mit fremden Reisepapieren aufgetreten. Zwar mag er heute wegen der geschlossenen Ehe und des beantragten Nachzugsgesuchs ein Interesse daran haben, auffindbar zu bleiben. Allerdings wird auf die Ausführungen in obiger Erwägung 6.5 verwiesen (Hinweise auf Scheinehe und Delikte). Zudem hatte ihn auch ein laufendes Asylgesuch im Jahre 2006 nicht davon abgehalten, längere Zeit unterzutauchen. Wie schon das Bundesverwaltungsgericht in seinem Urteil vom 31. Oktober 2008 (dort E. 4.3) festgehalten hat, hat er sich mit keinem Wort dazu geäussert, weshalb er seinerzeit spurlos verschwunden war. Dieses Gericht hat im Übrigen geschlossen, dass er keine asylrelevanten Verfolgungsvorbringen "glaubhaft" gemacht hatte. Unter diesen Umständen ist nicht zu beanstanden, wenn die Vorinstanzen von einer Untertauchensgefahr ausgehen. Dass der Beschwerdeführer gelegentlich behördlichen Anweisungen folgt, schliesst diesen Haftgrund noch nicht aus.
8. Aufgrund der Gesamtumstände erweist sich die bewilligte Ausschaffungshaft als verhältnis- und bundesrechtmässig. Die Beschwerde ist daher abzuweisen.
Diesem Ausgang entsprechend hätte der Beschwerdeführer die Verfahrenskosten zu tragen (<ref-law>). Seinem Gesuch auf unentgeltliche Rechtspflege und Verbeiständung ist jedoch gemäss <ref-law> stattzugeben, zumal sich das Bundesgericht unter dem neuen Ausländerrecht bisher nicht mit der Frage der Anordnung einer Ausschaffungshaft trotz bestehender Ehe mit einer Person, die über ein gefestigtes Anwesenheitsrecht in der Schweiz verfügt, zu befassen hatte; deshalb erschien das Rechtsbegehren nicht von vornherein aussichtslos. Aufgrund der vom Beschwerdeführer nachgereichten Belege der Arbeitslosenkasse ist von einer Bedürftigkeit des Beschwerdeführers und seiner Ehefrau auszugehen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen:
2.1 Es werden keine Kosten erhoben.
2.2 Rechtsanwalt Jean-Pierre Menge, Chur, wird für das bundesgerichtliche Verfahren als unentgeltlicher Rechtsbeistand eingesetzt und aus der Bundesgerichtskasse mit Fr. 1'500.-- entschädigt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt des Kantons Zürich, dem Bezirksgericht Zürich, Haftrichter, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 13. Februar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Merz