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.