Sachverhalt: A. A.a. Dem algerischen Staatsangehörigen A._ (geb. 1973) widerrief das Migrationsamt des Kantons Basel-Stadt am 4. Februar 2014 die gestützt auf die Ehe mit einer Schweizer Bürgerin erteilte Aufenthaltsbewilligung und wies ihn aus der Schweiz weg. Ein kantonales Rechtsmittel hiegegen blieb erfolglos. Zur Sicherstellung dieser Wegweisung wurde A._ am 23. September 2014 in Ausschaffungshaft genommen; auf die gegen den richterlichen Haftgenehmigungsentscheid erhobene Beschwerde trat das Bundesgericht am 14. Oktober 2014 nicht ein (Urteil 2C_939/2014). Am 23. Oktober 2014 wurde A._ nach Algerien ausgeschafft. A.b. Am 26. November 2015 nahm die Kantonspolizei Basel-Stadt A._ in der Notschlafstelle Y._ fest; gleichentags wurde er durch die Staatsanwaltschaft und das Migrationsamt befragt. Ebenso ordnete das Migrationsamt eine Ausschaffungshaft für drei Monate (bis zum 26. Februar 2016) an, welche mit Urteil des basel-städtischen Einzelrichters für Zwangsmassnahmen im Ausländerrecht vom 27. November 2015 für rechtmässig befunden wurde. A.c. Mit Verfügung vom 9. Februar 2016 ordnete das Migrationsamt gegenüber A._ eine Verlängerung der Ausschaffungshaft um drei Monate (bis zum 25. Mai 2016) an. Diese wurde vom zuständigen Einzelrichter anlässlich einer mündlichen Verhandlung im Gefängnis X._ überprüft und mit Urteil vom 25. Februar 2016 für rechtmässig befunden. B. Mit Eingabe vom 21. März 2016 beantragt A._ dem Bundesgericht, das letztgenannte Urteil aufzuheben und ihn umgehend aus der Haft zu entlassen. Der Einzelrichter und das SEM äussern sich, ohne einen ausdrücklichen Antrag zu stellen. Der Beschwerdeführer hält an seinen Anträgen fest.