Ausschaffungshaft gemäss Art. 13b ANAG, hat sich ergeben: A.- Am 8. Februar 2000 nahm der deutsche Bundesgrenzschutz im ICE 76 von Basel nach Frankfurt einen Ausländer fest, der sich bei der Grenzkontrolle nicht ausweisen konnte. Der Ausländer musste überwältigt werden, da er Widerstand leistete und vorgab, bewaffnet zu sein, was allerdings, wie sich nachträglich herausstellte, nicht zutraf. Der Ausländer gab sich als italienischer Staatsangehöriger mit Namen M._, geb. 24. Juni (oder Juli) 1965, aus. Aufgrund des Rückübernahmeabkommens zwischen der Bundesrepublik Deutschland und der Schweiz wurde er unverzüglich der Kantonspolizei Basel-Stadt zugeführt. Vor dieser und bei der Einvernahme am 9. Februar 2000 durch die Einwohnerdienste des Kantons Basel-Stadt, Abteilung Internationale Kundschaft als Fremdenpolizei, bezeichnete er sich erneut als italienischer Staatsangehöriger namens O._, geboren am 24. oder 27. Juni 1965, beharrte aber darauf, dass die Einvernahme in französischer und nicht in italienischer Sprache durchgeführt wurde. Die Einwohnerdienste verfügten gleichentags die Wegweisung von O._ und ordneten eine dreimonatige Ausschaffungshaft an. Die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht am Verwaltungsgericht des Kantons Basel-Stadt genehmigte diese Haft am 11. Februar 2000 lediglich für 14 Tage, weil aufgrund des merkwürdigen Verhaltens des Ausländers nicht klar sei, ob er dem Verfahren geistig gewachsen sei oder nur vorspiegele, verwirrt zu sein; für eine allfällige weitere Verhandlung erging die Auflage, O._ von Amtes wegen einen Vertreter beizugeben. Ebenfalls am 11. Februar 2000 teilte der Delegato di polizia Chiasso mit, dass O._ der italienischen Polizei nicht bekannt sei und dass die italienischen Behörden die Rückübernahme verweigerten. In der Folge entliessen die Einwohnerdienste O._ am 14. Februar 2000 aus der Haft mit der Anweisung, die Schweiz zu verlassen. B.- O._ kam der Anweisung zur Ausreise nicht nach. Am 24. Februar 2000 meldete er sich bei der Fremdenpolizei und gab an, einen auf ihn lautenden - und in Wahrheit nicht existierenden - Ausweis über die Aufenthaltsbewilligung verloren zu haben. In der Folge wurde er wiederum festgehalten. Neu gab er sich als rumänischer Staatsangehöriger namens M._ aus, geb. am 27. Juni 1965 in Budapest, wobei er später ausführte, Bukarest gemeint zu haben. Die rumänische Sprache schien er allerdings nicht zu verstehen, dafür sprach er nunmehr Deutsch. Noch am gleichen Tag, am 24. Februar 2000, wiesen die Einwohnerdienste M._ daher erneut weg und verfügten wiederum Ausschaffungshaft, diesmal bis zum 23. Mai 2000. Am 28. Februar 2000 prüfte und bestätigte die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht am Verwaltungsgericht des Kantons Basel-Stadt die Haft. C.- Am 1. März 2000 richtete M._ eine handschriftliche Eingabe in deutscher Sprache an die Haftrichterin, worin er ein gewisses Fehlverhalten zugibt und um Haftentlassung ersucht. Da die für ein Haftentlassungsgesuch erforderliche Frist nicht abgelaufen war, leitete die Haftrichterin das Schreiben an das Bundesgericht weiter zur Prüfung, ob es als Verwaltungsgerichtsbeschwerde gegen den Haftentscheid zu behandeln sei. In der Folge eröffnete der Präsident der II. öffentlichrechtlichen Abteilung des Bundesgerichts den Schriftenwechsel zur Eingabe von M._. Die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht am Verwaltungsgericht des Kantons Basel-Stadt hat auf eine Stellungnahme verzichtet. Der Rechtsdienst der Einwohnerdienste des Kantons Basel-Stadt schliesst in seiner Vernehmlassung auf Abweisung der Beschwerde. Das Eidgenössische Justiz- und Polizeidepartement hat sich innert Frist nicht vernehmen lassen. Der Beschwerdeführer nahm die Gelegenheit nicht wahr, sich nochmals zur Sache zu äussern. D.- Am 13. März 2000 ging beim Bundesgericht ein weiteres handschriftliches Schreiben in deutscher Sprache ein, worin M._ ausführt, Anzeige gegen den Oberaufseher erheben zu wollen, der angeblich das Protokoll eines Gesprächs an Stelle von M._ gegen Entgelt durch einen anderen Aufseher habe unterschreiben lassen.