Sachverhalt: Sachverhalt: A. Der am ... 1978 geborene, aus Bangladesh stammende X._ reiste gemäss eigenen Angaben am 15. Juni 1998 von Italien her kommend in die Schweiz ein und stellte gleichentags unter dem Aliasnamen Y._ ein Asylgesuch. Mit Verfügung vom 13. November 1998 lehnte das Bundesamt für Flüchtlinge das Asylgesuch ab und wies Y._ aus der Schweiz weg. Mit Urteil vom 15. Januar 1999 trat die Schweizerische Asylrekurskommission auf die dagegen erhobene Beschwerde nicht ein. X._ alias Y._ reiste in der Folge nicht aus der Schweiz aus. Am 20. März 2001 teilte das Amt für öffentliche Sicherheit des Kantons Solothurn dem Bundesamt für Flüchtlinge mit, Y._ gelte seit dem 9. März 2001 als verschwunden. A. Der am ... 1978 geborene, aus Bangladesh stammende X._ reiste gemäss eigenen Angaben am 15. Juni 1998 von Italien her kommend in die Schweiz ein und stellte gleichentags unter dem Aliasnamen Y._ ein Asylgesuch. Mit Verfügung vom 13. November 1998 lehnte das Bundesamt für Flüchtlinge das Asylgesuch ab und wies Y._ aus der Schweiz weg. Mit Urteil vom 15. Januar 1999 trat die Schweizerische Asylrekurskommission auf die dagegen erhobene Beschwerde nicht ein. X._ alias Y._ reiste in der Folge nicht aus der Schweiz aus. Am 20. März 2001 teilte das Amt für öffentliche Sicherheit des Kantons Solothurn dem Bundesamt für Flüchtlinge mit, Y._ gelte seit dem 9. März 2001 als verschwunden. B. Am 5. Februar 2002 nahm die Kantonspolizei Basel-Stadt X._ alias Y._ in Basel fest. Am 6. Februar 2002 nahm ihn das Amt für öffentliche Sicherheit des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 8. Februar 2002 prüfte und genehmigte der Vizepräsident des Verwaltungsgerichts des Kantons Solothurn als Haftrichter die Ausschaffungshaft bis zum 5. Mai 2002. Mit Schreiben vom 20. März 2002 ersuchte X._ alias Y._ um Entlassung aus der Ausschaffungshaft; er räumte ein, dass er bisher unter einem falschen Namen aufgetreten sei und legte Kopien von Identitätspapieren vor; mit Schreiben vom 21. März 2002 sandte er die entsprechenden Originale nach. Er teilte zudem mit, er habe vor, seine über die Niederlassungsbewilligung verfügende Freundin Z._ in Bangladesh zu heiraten und im Anschluss daran ein ordentliches Familiennachzugsgesuch zu stellen. Mit Urteil vom 3. April 2002 wies der Vizepräsident des Verwaltungsgerichts das Haftentlassungsgesuch ab. Am 3. Mai 2002 genehmigte der Präsident des Verwaltungsgerichts eine Haftverlängerung bis zum 5. August 2002. Am 26. Juni 2002 wies der Vizepräsident des Verwaltungsgerichts ein weiteres Haftentlassungsgesuch ab. Am 31. Juli 2002 entliess das Amt für öffentliche Sicherheit, Ausländerfragen, X._ aus der Ausschaffungshaft, hielt ihn aber dazu an, sich alle zwei Wochen im Asylbüro zu melden. B. Am 5. Februar 2002 nahm die Kantonspolizei Basel-Stadt X._ alias Y._ in Basel fest. Am 6. Februar 2002 nahm ihn das Amt für öffentliche Sicherheit des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 8. Februar 2002 prüfte und genehmigte der Vizepräsident des Verwaltungsgerichts des Kantons Solothurn als Haftrichter die Ausschaffungshaft bis zum 5. Mai 2002. Mit Schreiben vom 20. März 2002 ersuchte X._ alias Y._ um Entlassung aus der Ausschaffungshaft; er räumte ein, dass er bisher unter einem falschen Namen aufgetreten sei und legte Kopien von Identitätspapieren vor; mit Schreiben vom 21. März 2002 sandte er die entsprechenden Originale nach. Er teilte zudem mit, er habe vor, seine über die Niederlassungsbewilligung verfügende Freundin Z._ in Bangladesh zu heiraten und im Anschluss daran ein ordentliches Familiennachzugsgesuch zu stellen. Mit Urteil vom 3. April 2002 wies der Vizepräsident des Verwaltungsgerichts das Haftentlassungsgesuch ab. Am 3. Mai 2002 genehmigte der Präsident des Verwaltungsgerichts eine Haftverlängerung bis zum 5. August 2002. Am 26. Juni 2002 wies der Vizepräsident des Verwaltungsgerichts ein weiteres Haftentlassungsgesuch ab. Am 31. Juli 2002 entliess das Amt für öffentliche Sicherheit, Ausländerfragen, X._ aus der Ausschaffungshaft, hielt ihn aber dazu an, sich alle zwei Wochen im Asylbüro zu melden. C. Am 8. Januar 2004 übermittelte das Eidgenössische Justiz- und Polizeidepartement dem Amt für öffentliche Sicherheit des Kantons Solothurn eine Kopie der Geburtsurkunde von X._, eine Kopie des so genannten "National Certificate", beglaubigt im August 2003, eine Kopie seines am 16. Oktober 2003 ausgestellten Passes und eine Bestätigung seiner Mutter, wonach er noch ledig sei. Diese stammten von der schweizerischen Vertretung in Dhaka, welche die betreffenden Dokumente im Hinblick auf die geplante Eheschliessung überprüft hatte. C. Am 8. Januar 2004 übermittelte das Eidgenössische Justiz- und Polizeidepartement dem Amt für öffentliche Sicherheit des Kantons Solothurn eine Kopie der Geburtsurkunde von X._, eine Kopie des so genannten "National Certificate", beglaubigt im August 2003, eine Kopie seines am 16. Oktober 2003 ausgestellten Passes und eine Bestätigung seiner Mutter, wonach er noch ledig sei. Diese stammten von der schweizerischen Vertretung in Dhaka, welche die betreffenden Dokumente im Hinblick auf die geplante Eheschliessung überprüft hatte. D. Am 9. Januar 2004 befragte das Amt für öffentliche Sicherheit, Ausländerfragen, des Kantons Solothurn X._, konfrontierte ihn mit den Kopien des Passes und des National Certificate und eröffnete ihm, dass es ihn wiederum in Ausschaffungshaft nahmen werde. Hierauf forderte Z._ ihren Freund auf, mit ihr das Büro zu verlassen, worauf dieser davonlief. Als der befragende Beamte die Verfolgung aufnehmen wollte, stellte sich Z._ ihm in den Weg, worauf X._ entkam. Am 18. März 2004 nahm die Kantonspolizei Basel-Stadt X._ in der Wohnung seiner Freundin Z._ fest; tags darauf nahm ihn das Amt für öffentliche Sicherheit, Ausländerfragen, des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 22. März 2004 prüfte und genehmigte der Präsident des Verwaltungsgerichts des Kantons Solothurn die Ausschaffungshaft bis zum 17. Mai 2004. Am 18. März 2004 nahm die Kantonspolizei Basel-Stadt X._ in der Wohnung seiner Freundin Z._ fest; tags darauf nahm ihn das Amt für öffentliche Sicherheit, Ausländerfragen, des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 22. März 2004 prüfte und genehmigte der Präsident des Verwaltungsgerichts des Kantons Solothurn die Ausschaffungshaft bis zum 17. Mai 2004. E. Dagegen hat X._ am 25. März 2004 beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben. Er beantragt, das Urteil des Verwaltungsgerichts aufzuheben und ihn aus der Haft zu entlassen. Zudem ersucht er um unentgeltliche Rechtspflege und Verbeiständung. Das Departement des Innern, Abteilung Ausländerfragen, sowie das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde abzuweisen. Das Bundesamt für Flüchtlinge hat sich nicht vernehmen lassen. Mit Schreiben vom 1. April 2004 hält X._ am Antrag auf Haftentlassung fest. Das Departement des Innern, Abteilung Ausländerfragen, sowie das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde abzuweisen. Das Bundesamt für Flüchtlinge hat sich nicht vernehmen lassen. Mit Schreiben vom 1. April 2004 hält X._ am Antrag auf Haftentlassung fest. F. Mit Schreiben vom 25. März 2004 ersuchte X._ das Bundesamt für Flüchtlinge um Wiedererwägung seiner Wegweisungsverfügung vom 13. November 1998. F. Mit Schreiben vom 25. März 2004 ersuchte X._ das Bundesamt für Flüchtlinge um Wiedererwägung seiner Wegweisungsverfügung vom 13. November 1998. G. Mit Verfügung vom 26. März 2004 hat der Abteilungspräsident das Gesuch um sofortige Haftentlassung bzw. um aufschiebende Wirkung zur Zeit abgewiesen. 