Sachverhalt: A. X._ stellte am 17. Januar 2000 ein Asylgesuch in der Schweiz, wobei er angab, A._ zu heissen und aus Algerien zu stammen. Das Asylgesuch wurde gleichentags abgewiesen. Diesen Entscheid focht er nicht an; er ist in Rechtskraft erwachsen. Vom 25. November 2000 bis zum 12. März 2001 befand sich X._ in Ausschaffungshaft. Er entwich am 12. März 2001 aus der Psychiatrischen Klinik Hard. Am 8. April 2001 wurde er polizeilich angehalten und wegen eines Bisses durch einen Polizeihund ins Spital gebracht, von wo er flüchtete. Auch am 21. und 23. August 2001 entwich er jeweils, als er erneut angehalten und ins Spital gebracht wurde. Er verliess zwischenzeitlich gemäss eigener Darstellung die Schweiz und wurde am 28. Mai 2002 wieder verhaftet, nachdem er eigenen Angaben zufolge gleichentags mit einem gefälschten belgischen Reisepass in die Schweiz eingereist war. Er hatte immer wieder andere Identitäten verwendet und sich dabei unter Benutzung falscher Ausweise als Belgier, Algerier, Franzose und Palästinenser ausgegeben. Das Bezirksgericht Zürich bestrafte ihn am 29. Juli 2002 u.a. wegen mehrfacher Fälschung von Ausweisen und mehrfacher Hinderung einer Amtshandlung. Am 10. April 2003 war für ihn ein Flug nach Algier gebucht. Er verweigerte den Rückflug nach Algerien, weil die Angaben im algerischen Laissez-Passer nicht mit seiner Person übereinstimmten. Im Übrigen machte er nun geltend, Tunesier zu sein. A. X._ stellte am 17. Januar 2000 ein Asylgesuch in der Schweiz, wobei er angab, A._ zu heissen und aus Algerien zu stammen. Das Asylgesuch wurde gleichentags abgewiesen. Diesen Entscheid focht er nicht an; er ist in Rechtskraft erwachsen. Vom 25. November 2000 bis zum 12. März 2001 befand sich X._ in Ausschaffungshaft. Er entwich am 12. März 2001 aus der Psychiatrischen Klinik Hard. Am 8. April 2001 wurde er polizeilich angehalten und wegen eines Bisses durch einen Polizeihund ins Spital gebracht, von wo er flüchtete. Auch am 21. und 23. August 2001 entwich er jeweils, als er erneut angehalten und ins Spital gebracht wurde. Er verliess zwischenzeitlich gemäss eigener Darstellung die Schweiz und wurde am 28. Mai 2002 wieder verhaftet, nachdem er eigenen Angaben zufolge gleichentags mit einem gefälschten belgischen Reisepass in die Schweiz eingereist war. Er hatte immer wieder andere Identitäten verwendet und sich dabei unter Benutzung falscher Ausweise als Belgier, Algerier, Franzose und Palästinenser ausgegeben. Das Bezirksgericht Zürich bestrafte ihn am 29. Juli 2002 u.a. wegen mehrfacher Fälschung von Ausweisen und mehrfacher Hinderung einer Amtshandlung. Am 10. April 2003 war für ihn ein Flug nach Algier gebucht. Er verweigerte den Rückflug nach Algerien, weil die Angaben im algerischen Laissez-Passer nicht mit seiner Person übereinstimmten. Im Übrigen machte er nun geltend, Tunesier zu sein. B. Am 11. April 2003 verfügte das Migrationsamt des Kantons Zürich die Wegweisung von X._ alias B._ alias A._ alias C._ alias D._ aus dem Gebiet der Schweiz und ordnete die Ausschaffungshaft an. Der Haftrichter am Bezirksgericht Zürich bestätigte am 12. April 2003 im Anschluss an eine mündliche Verhandlung die Ausschaffungshaft und bewilligte diese bis zum 9. Juli 2003. B. Am 11. April 2003 verfügte das Migrationsamt des Kantons Zürich die Wegweisung von X._ alias B._ alias A._ alias C._ alias D._ aus dem Gebiet der Schweiz und ordnete die Ausschaffungshaft an. Der Haftrichter am Bezirksgericht Zürich bestätigte am 12. April 2003 im Anschluss an eine mündliche Verhandlung die Ausschaffungshaft und bewilligte diese bis zum 9. Juli 2003. C. Dagegen führte X._ alias A._ am 12. Mai 2003 Verwaltungsgerichtsbeschwerde beim Bundesgericht. Er beantragt seine Haftentlassung und stellt ein Gesuch um unentgeltliche Rechtspflege wegen offensichtlicher Mittellosigkeit. Das Migrationsamt des Kantons Zürich beantragt, die Beschwerde abzuweisen. Das Bezirksgericht Zürich, Haftrichter, verzichtet auf eine Vernehmlassung. Der Beschwerdeführer hat am 21. Mai 2003 eine Stellungnahme eingereicht. Das Bundesamt für Flüchtlinge liess sich innert Frist nicht vernehmen. 