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.

Das Bundesgericht zieht in Erwägung:
1.- Nach Art. 13c Abs. 4 ANAG kann der inhaftierte Ausländer frühestens einen Monat nach der Haftüberprüfung ein Haftentlassungsgesuch einreichen. Nachdem das Hafturteil der basel-städtischen Einzelrichterin für Zwangsmassnahmen im Ausländerrecht am 28. Februar 2000 ergangen ist und die als Haftentlassungsgesuch bezeichnete Eingabe bereits vom 1. März 2000 stammt, ist die einmonatige Frist gemäss Art. 13c Abs. 4 ANAG offensichtlich nicht eingehalten. Die Eingabe kann hingegen vom Bundesgericht, an welches sie weitergeleitet worden ist, als Verwaltungsgerichtsbeschwerde gegen das Hafturteil entgegengenommen werden. Gegen einen kantonal letztinstanzlichen Haftrichterentscheid steht nämlich die Verwaltungsgerichtsbeschwerde an das Bundesgericht offen (<ref-ruling> E. 2b S. 371 f., mit Hinweisen). Die fragliche Eingabe ist innert der dafür erforderlichen Frist von 30 Tagen (Art. 106 Abs. 1 OG) ergangen und enthält sinngemäss den Antrag auf Haftentlassung sowie eine, wenn auch rudimentäre, so doch knapp genügende Begründung, womit sie die gesetzlichen Anforderungen an die Form der Verwaltungsgerichtsbeschwerde (vgl. Art. 108 OG) gerade noch erfüllt.
2.- a) Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, soweit die Voraussetzungen von Art. 13b ANAG erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl.
BGE 121 II 59 E. 2 S. 61; <ref-ruling> ff.), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist (<ref-ruling> E. 3a S. 374, 377 E. 2a S. 379). Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 3a S. 374, 377 E. 3a S. 381; <ref-ruling> E. 1 S. 3). Nach Art. 13b Abs. 1 lit. c ANAG kann Ausschaffungshaft insbesondere verfügt werden, wenn konkrete Anzeichen befürchten lassen, dass sich der Ausländer der Ausschaffung entziehen will (Gefahr des Untertauchens). Das trifft namentlich zu, wenn der Ausländer bereits einmal untergetaucht ist, behördlichen Anordnungen keine Folge leistet, durch erkennbar unglaubwürdige und widersprüchliche Angaben die Vollzugsbemühungen der Behörden erschwert oder sonst wie klar zu erkennen gibt, keinesfalls in sein Herkunftsland zurückkehren zu wollen (<ref-ruling> E. 3b/aa S. 375).
b) Der Beschwerdeführer hat sich gegenüber den Behörden nicht nur passiv verhalten, sondern mehrfach aktiv versucht, die Behörden zu täuschen oder jedenfalls zu verwirren.
Namentlich hat er verschiedene Identitäten und Herkünfte angeführt. Obwohl sich die angegebenen Namen nur geringfügig unterscheiden, betrifft dies doch nicht nur die Schreibweise, sondern hat auch in phonetischer und sprachanalytischer Hinsicht deutliche Auswirkungen. Weiter wollte der Beschwerdeführer zunächst aus Italien stammen, wobei er sich aber weigerte, die italienische Sprache zu benutzen.
Danach gab er an, Rumäne zu sein, bezeichnete aber Budapest als seinen Geburtsort, was er später als Verwechslung mit Bukarest darstellte. Ursprünglich erklärte er sodann, aus Marokko nach Italien eingereist zu sein, was er später ebenfalls anders darstellte. Der Beschwerdeführer versteht die französische und die deutsche Sprache. Wie seine Eingaben belegen, vermag er sich in letzterer sogar leidlich schriftlich auszudrücken.
Das Verhalten des Beschwerdeführers in der Zeit zwischen den beiden Inhaftierungen zeigt sodann, dass er die hiesigen Verhältnisse recht gut kennt. Diese Kenntnisse kann er kaum in seinem angeblich lediglich rund 14-tägigen Aufenthalt in der Schweiz erworben haben. Um sich Medikamente zu verschaffen, hat er sich in einer Apotheke als Mitglied einer bestimmten Krankenkasse ausgegeben und so die Bezahlung umgangen. Wenn er damit auch nicht eigentliche Behörden getäuscht hat, so lässt dies doch darauf schliessen, dass er sich auch nicht ohne weiteres behördlichen Vorkehren unterziehen würde. Bei den Einwohnerdiensten hat er den angeblichen Verlust seines B-Ausweises gemeldet, obwohl er nie über eine Aufenthaltsbewilligung in der Schweiz verfügte. Auch sein übriges Verhalten vor den Fremdenpolizeibehörden lässt darauf schliessen, dass er ganz bewusst und zielgerichtet darauf hin arbeitet, in der Schweiz bleiben zu können.
Schliesslich geht aus seinem Verhalten im Intercity-Zug, als er sich der Festnahme durch den deutschen Bundesgrenzschutz auf heimtückische Weise widersetzte, sodass letztlich ein behördlicher Gewalteinsatz erforderlich war, eine gewisse Bereitschaft hervor, sich gegen behördliche Anordnungen zur Wehr zu setzen. Insgesamt bestehen somit genügend Anhaltspunkte, welche die Annahme von Untertauchensgefahr zulassen.
c) Im Übrigen stellt sich einzig die Frage, ob der Beschwerdeführer wieder in Haft genommen werden durfte, nachdem er sich bereits einmal in Ausschaffungshaft befand und zwischenzeitlich entlassen worden war. Nach der bundesgerichtlichen Rechtsprechung setzt eine erneute Inhaftierung voraus, dass sich die Ausgangslage nachträglich in entscheidender Weise geändert hat (Alain Wurzburger, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in RDAF 1997 I S. 341; Andreas Zünd, Die Rechtsprechung des Bundesgerichts zu den Zwangsmassnahmen im Ausländerrecht, in ZBJV 132/1996 S. 80). Im Zusammenhang mit dem Haftgrund der Untertauchensgefahr bedarf es neuer Indizien, die erst nach der ersten Inhaftierung eingetreten sind. Diese Voraussetzung ist im vorliegenden Fall freilich erfüllt. Nachdem ursprünglich Zweifel am geistigen Zustand des Beschwerdeführers bestanden, hat sein späteres Verhalten gezeigt, dass diese nicht aufrechtzuerhalten waren. Insbesondere aber hat der Beschwerdeführer sein täuschendes Verhalten auch nach der Entlassung aus der ersten Ausschaffungshaft fortgesetzt. Wesentliche Auskünfte zu seiner Identität und Herkunft, die mit früheren Angaben im Widerspruch stehen, ergingen erst bei den Einvernahmen im zweiten Haftverfahren.
Damit ergab sich eine neue Ausgangslage und durfte der Beschwerdeführer erneut in Ausschaffungshaft genommen werden.
3.- a) Die Verwaltungsgerichtsbeschwerde erweist sich als unbegründet und ist abzuweisen.
b) Bei diesem Verfahrensausgang würde der Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 OG). Es rechtfertigt sich jedoch mit Blick auf seine finanziellen Verhältnisse, von der Erhebung einer Gerichtsgebühr abzusehen (Art. 153a Abs. 1 OG).
c) Mit als Anzeige bezeichneter Eingabe vom 10. März 2000 an das Bundesgericht trägt der Beschwerdeführer ein angeblich unkorrektes Verhalten des Gefängnispersonals vor. Es ist zwar zu vermuten, dass entgegen der Auffassung des Beschwerdeführers nicht seine Unterschrift gefälscht wurde, sondern es lediglich darum ging, durch eine Drittperson unterschriftlich bestätigen zu lassen, dass er die Unterzeichnung eines bestimmten Schriftstückes verweigerte.
Da sich dieses anscheinend auf ein Gespräch vom 10. März 2000 bezog, ist es im vorliegenden Verfahren, in dem tatsächliche Ereignisse, die nach dem haftrichterlichen Urteil stattgefunden haben, nicht berücksichtigt werden können (vgl. <ref-ruling> E. 3a, mit Hinweisen), in der Sache jedenfalls nicht wesentlich. Für die Anzeige als solche ist zudem ohnehin nicht das Bundesgericht, sondern die entsprechende kantonale Aufsichtsbehörde zuständig. Die Eingabe ist daher zuständigkeitshalber an das Polizei- und Militärdepartement des Kantons Basel-Stadt zu überweisen und der Ergänzung halber in Kopie der Haftrichterin und den Einwohnerdiensten zur Kenntnisnahme zuzustellen.
c) Die Einwohnerdienste werden ersucht, sicherzustellen, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und verständlich gemacht wird.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Es werden keine Kosten erhoben.
3.- Die Eingabe des Beschwerdeführers vom 10. März 2000 wird dem Polizei- und Militärdepartement des Kantons Basel-Stadt überwiesen und den Einwohnerdiensten des Kantons Basel-Stadt, Abteilung Internationale Kundschaft als Fremdenpolizei, sowie dem Verwaltungsgericht des Kantons Basel-Stadt, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, in Kopie zur Kenntnisnahme zugestellt.
4.- Dieses Urteil wird dem Beschwerdeführer, den Einwohnerdiensten des Kantons Basel-Stadt, Abteilung Internationale Kundschaft als Fremdenpolizei, dem Verwaltungsgericht des Kantons Basel-Stadt, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, dem Polizei- und Militärdepartement des Kantons Basel-Stadt sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
_
Lausanne, 16. März 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: