Ausschaffungshaft gemäss Art. 13b ANAG, hat sich ergeben:
A.-K._, geb. 11. November 1960, Staatsangehöriger von Gabun, reiste 1991 in die Schweiz ein und stellte ein Asylgesuch. Dieses wurde abgewiesen und K._ aus der Schweiz weggewiesen. Die Schweizerische Asylrekurskommission wies eine gegen die entsprechende Verfügung des Bundesamtes für Flüchtlinge erhobene Beschwerde am 5. Januar 1994 rechtskräftig ab. In den Jahren 1996 und 1997 befand sich K._ sowohl im Kanton Zürich als auch im Kanton Bern in Ausschaffungshaft.
Im Jahre 1996 wurde K._ wegen Widerhandlung gegen das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) zu drei Tagen Gefängnis sowie in den Jahren 1998 und 1999 zur Hauptsache aus demselben Grund sowie wegen Verstosses gegen das Betäubungsmittelgesetz zu bedingt ausgesprochenen Freiheitsstrafen von drei und elf Monaten Gefängnis verurteilt. Am 4. Mai 1998 bestrafte ihn der Gerichtspräsident 15 des Gerichtskreises VIII Bern-Laupen wegen Betrugs, Urkundenfälschung, unrechtmässiger Aneignung und Widerhandlung gegen das Strassenverkehrsgesetz zu vier Monaten Gefängnis bei bedingtem Vollzug und zu fünf Jahren unbedingter Landesverweisung. Am 13. Oktober 1999 widerrief das Bezirksgericht Winterthur den bedingten Aufschub dieser letzten Freiheitsstrafe.
Vom 1. Februar 2000 an befand sich K._ im Strafvollzug. Am 17. April 2000 ordnete der Regierungsstatthalter I von Bern die Ausschaffungshaft auf den Zeitpunkt der Entlassung an, und tags darauf stellte er entsprechenden Antrag beim Haftgericht III Bern-Mittelland. Am 28. April 2000 (schriftliches Urteil vom 2. Mai 2000) prüfte und bestätigte der Haftrichter 5 am Haftgericht III Bern-Mittelland die Haft. Am 29. April 2000 wurde K._ bedingt aus dem Strafvollzug entlassen, wobei der Vollzug der ihm auferlegten Landesverweisung nicht aufgeschoben wurde; am gleichen Tag wurde K._ in Ausschaffungshaft genommen.
B.- Mit Verwaltungsgerichtsbeschwerde vom 7. Mai 2000 an das Bundesgericht beantragt K._, das Hafturteil vom 28. April/2. Mai 2000 sei aufzuheben und er sei umgehend aus der Haft zu entlassen. Zudem stellte er ein Gesuch um sofortige Haftentlassung ohne Anhörung der kantonalen Behörden im Sinne einer superprovisorischen Massnahme.
Der Regierungsstatthalter I von Bern sowie der Haftrichter 5 am Haftgericht III Bern-Mittelland schliessen 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.
C.- Mit prozessleitender Verfügung vom 8. Mai 2000 lehnte es der Präsident der II. öffentlichrechtlichen Abteilung ab, K._ sofort ohne Anhörung der kantonalen Behörden aus der Haft zu entlassen.
D.- Nachdem der Instruktionsrichter festgestellt hatte, dass die Akten lediglich - von K._ eingereichte - Belege für eine Ausschaffungshaft während der Dauer von rund acht Monaten im Kanton Zürich enthielten, zog er bei der Fremdenpolizei des Kantons Zürich Erkundigungen über die wirkliche Dauer der ersten Ausschaffungshaft in den Jahren 1996/1997 ein. Es ergab sich, dass sich K._ vom 11. Juli 1996 bis zum 7. März 1997 im Kanton Zürich in Ausschaffungshaft befunden hatte. Die Verfahrensbeteiligten erhielten Gelegenheit, sich nochmals zur Sache zu äussern. Der Regierungsstatthalter I von Bern sowie der Haftrichter 5 am Haftgericht III Bern-Mittelland machen geltend, jedenfalls könne die maximale Haftdauer von neun Monaten ausgeschöpft werden, im Übrigen sei aber auch über die Zulässigkeit der Anordnung einer überhaupt neuen Ausschaffungshaft zu befinden. K._ beharrte auf seinem Standpunkt und führte aus, zusätzlich im Jahre 1998 einen weiteren Monat im Kanton Bern in Ausschaffungshaft gewesen zu sein. Eine zusätzliche Erkundigung des Instruktionsrichters bei der Fremdenpolizei der Stadt Bern ergab, dass K._ dort in der Tat die Zeit vom 29. Oktober bis zum 27. November 1997 (nicht: 1998) in Ausschaffungshaft verbracht hatte.

Das Bundesgericht zieht in Erwägung:
1.- Zusammen mit den Unterlagen zur Ausschaffungshaft vom Oktober/November 1997 reichte die Fremdenpolizei der Stadt Bern dem Bundesgericht das Urteil des Bezirksgerichts Winterthur vom 13. Oktober 1999 ein, welches sich vorher nicht in den Akten befunden hatte. Ob bereits die Vorinstanzen das Urteil von Amtes wegen hätten beiziehen müssen, kann offen bleiben. Jedenfalls geht daraus hervor, dass der Beschwerdeführer mit diesem Urteil unter anderem wegen Betäubungsmittelhandels sowie wegen Missachtung einer Ausgrenzung verurteilt worden ist. Der Beschwerdeführer war schon im Strafprozess durch denselben Anwalt vertreten wie im vorliegenden Haftverfahren; das Strafurteil ist demnach sowohl ihm als auch seinem Rechtsvertreter bekannt. Im Übrigen braucht dem Beschwerdeführer angesichts des Ausgangs des vorliegenden Verfahrens nicht nochmals Gelegenheit zur Stellungnahme gegeben zu werden.
2.- Der Beschwerdeführer befand sich bereits vom 11. Juli 1996 bis zum 7. März 1997 (im Kanton Zürich) sowie vom 29. Oktober bis zum 27. November 1997 (im Kanton Bern) in Ausschaffungshaft. Aus der schriftlichen Urteilsbegründung vom 11. November 1997 des Haftrichterurteils vom 3. November 1997 geht hervor, dass der Haftrichter damals annahm, eine weitere Haft sei lediglich noch für höchstens einen Monat zulässig, weil der Beschwerdeführer bereits vom 10. Juli 1996 bis zum 7. März 1997 in Haft gewesen sei. Unter diesen Umständen, und da der Beschwerdeführer sich inzwischen ohnehin wesentlich länger als ein paar Tage erneut in Ausschaffungshaft befindet, ist es nicht am Bundesgericht, im vorliegenden Verfahren darüber zu befinden, ob die Haft allenfalls noch für drei oder vier Tage hätte angeordnet werden dürfen. Zu entscheiden ist vielmehr, ob die Neuanordnung einer Ausschaffungshaft überhaupt zulässig ist, wie dies sowohl der Regierungsstatthalter als auch der Haftrichter angenommen haben.
3.- Nach Art. 13b Abs. 2 ANAG darf die Ausschaffungshaft erstmalig für höchstens drei Monate angeordnet und danach um höchstens sechs Monate verlängert werden. Insgesamt gilt somit eine absolute Höchstdauer von neun Monaten.
Ob ein Ausländer, der sich bereits während neun Monaten in Ausschaffungshaft befunden hat, erneut inhaftiert werden darf, ist eine heikle Rechtsfrage. Abgesehen vom Fall, in welchem der Ausländer nach der ersten Haft ausgereist ist, womit die ursprüngliche Entfernungsmassnahme vollzogen wurde, danach wieder eingereist und nunmehr mit einer neuen Entfernungsverfügung belegt ist (vgl. <ref-ruling> E. 3b; Andreas Zünd, Zwangsmassnahmen im Ausländerrecht:
Verfahrensfragen und Rechtsschutz, in AJP 1995 S. 865), kommt eine erneute Ausschaffungshaft, wenn überhaupt, dann höchstens unter engen Voraussetzungen in Frage. Wie es sich damit verhält, kann im vorliegenden Fall jedoch dahingestellt bleiben, da die vorliegende Beschwerde ohnehin aus einem anderen Grund gutgeheissen werden muss.
4.- a) Gemäss Art. 13c Abs. 5 lit. a ANAG darf die Ausschaffungshaft nur angeordnet oder aufrechterhalten werden, wenn der Vollzug der Weg- oder Ausweisung nicht aus rechtlichen oder tatsächlichen Gründen undurchführbar ist. Die Haft ist im Sinne dieser Bestimmung unzulässig, wenn für die Undurchführbarkeit des Vollzugs der Wegweisung triftige Gründe vorliegen oder praktisch feststeht, dass er sich innert der gesetzlich vorgesehenen Haftdauer nicht realisieren lässt (<ref-ruling> E. 3 S. 152 f.).
b) Seit dem 5. Januar 1994 besteht gegen den Beschwerdeführer eine rechtskräftige Entfernungsmassnahme.
Während nunmehr über sechs Jahren konnte diese nicht vollzogen werden. Zumindest seit rund vier Jahren stand der Beschwerdeführer den Behörden wiederholt zwangsweise zur Verfügung.
Weder während der achtmonatigen Dauer der ersten Ausschaffungshaft durch den Kanton Zürich noch während der nochmaligen Einsperrung für einen Monat im Kanton Bern liess sich die Ausschaffung jedoch durchführen. Ebenso wenig gelang es während des rund dreimonatigen Strafvollzugs trotz entsprechender behördlicher Bemühungen, Reisepapiere für den Beschwerdeführer zu beschaffen. Auch die Annahme des Haftrichters im angefochtenen Entscheid, ein Reisepapier sei heute einfacher zu beschaffen als früher, sowie die Aussage des Regierungsstatthalters in seiner Eingabe vom 22. Mai 2000 an das Bundesgericht, die Beschaffung der nötigen Reisepapiere liege offenbar demnächst im Bereich des Möglichen, sind nicht belegt.
Sodann hat das Bezirksgericht Winterthur den Beschwerdeführer am 13. Oktober 1999 unter anderem in Anwendung von Art. 23a in Verbindung mit Art. 13e Abs. 1 ANAG wegen Missachtung einer Ausgrenzung verurteilt. Gemäss Art. 23a ANAG wird dafür vorausgesetzt, dass der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar ist. Dieses Erfordernis beruht auf dem Prinzip des Vorrangs der Ausschaffung vor der Bestrafung und schränkt das strafprozessuale Legalitätsprinzip ein (vgl. <ref-ruling>; <ref-ruling>). Eine Kumulation von strafrechtlicher Sanktion und Ausschaffungshaft ist - angesichts der gegengleichen Voraussetzungen in Art. 13c Abs. 5 lit. a sowie in Art. 23a ANAG - ausgeschlossen (unveröffentlichtes Urteil des Bundesgerichts vom 29. Mai 1997 i.S. Alatrash).
Dass eine strafrechtliche Verurteilung wegen Missachtung der Ausgrenzung vorliegt, welche der Ausländer anzufechten unterlassen hat, schliesst die nachträgliche Anordnung ausländerrechtlicher Haft zwar nicht zwingend aus (unveröffentlichtes Urteil des Bundesgerichts vom 6. April 1999 i.S.
Kenan); wenn dies aber wie im vorliegenden Fall mit den übrigen tatsächlichen Gegebenheiten, welche ebenfalls die Undurchführbarkeit der Ausschaffung indizieren, im Einklang steht, lässt es sich in entsprechendem Sinne mit berücksichtigen.
Aus allen diesen Umständen ergibt sich mit genügender Deutlichkeit, dass die verschiedenen Entfernungsmassnahmen im vorliegenden Zusammenhang - jedenfalls zurzeit - als tatsächlich undurchführbar zu gelten haben.
c) Angesichts dieser Rechtslage dürfte der Beschwerdeführer immerhin auch künftig in Anwendung von Art. 23a ANAG bestraft werden können, sollte er erneut die wohl weiterhin gültige Ausgrenzung oder eine allenfalls andere neue Auflage nach Art. 13e ANAG missachten.
5.- Die Verwaltungsgerichtsbeschwerde ist gutzuheissen und der Beschwerdeführer unverzüglich aus der Haft zu entlassen.
Weil der Beschwerdeführer obsiegt, ist keine Gerichtsgebühr zu erheben (Art. 156 Abs. 2 OG). Hingegen hat ihm der Kanton Bern für das bundesgerichtliche Verfahren eine Parteientschädigung auszurichten (vgl. Art. 159 Abs. 1 und 2 OG). Damit wird das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird gutgeheissen, und der Entscheid des Haftgerichts III Bern-Mittelland, Haftrichter 5, vom 28. April/2. Mai 2000 wird aufgehoben.
2.- Der Beschwerdeführer ist unverzüglich aus der Haft zu entlassen.
3.- Es werden keine Kosten erhoben.
4.- Der Kanton Bern hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
5.- Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
6.- Dieses Urteil wird dem Beschwerdeführer, dem Regierungsstatthalter I von Bern und dem Haftgericht III Bern-Mittelland, Haftrichter 5, sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
_
Lausanne, 25. Mai 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: