Das Bundesgericht stellt fest und zieht in Erwägung:
Das Bundesgericht stellt fest und zieht in Erwägung:
Das Bundesgericht stellt fest und zieht in Erwägung:
1.1 Am 5. Februar 2004 nahm der Migrationsdienst des Kantons Bern den nach eigenen Angaben aus Georgien/Abchasien stammenden X._ (geb. 1971) in Ausschaffungshaft. Das Haftgericht III Bern-Mittelland prüfte und genehmigte diese am 9. Februar 2004. Das Bundesgericht wies eine hiergegen gerichtete Verwaltungsgerichtsbeschwerde am 10. März 2004 ab (2A.130/2004).
1.2 Mit Entscheid vom 6. Mai 2004 verlängerte das Haftgericht III Bern-Mittelland die Ausschaffungshaft von X._ um weitere drei Monate. X._ beantragt in einer auf Russisch abgefassten, von Amtes wegen übersetzten Eingabe an das Bundesgericht, diesen Entscheid aufzuheben und ihn aus der Haft zu entlassen.
1.2 Mit Entscheid vom 6. Mai 2004 verlängerte das Haftgericht III Bern-Mittelland die Ausschaffungshaft von X._ um weitere drei Monate. X._ beantragt in einer auf Russisch abgefassten, von Amtes wegen übersetzten Eingabe an das Bundesgericht, diesen Entscheid aufzuheben und ihn aus der Haft zu entlassen.
2. Die Eingabe ist, soweit sich der Beschwerdeführer darin überhaupt sachbezogen mit dem angefochtenen Entscheid auseinandersetzt (vgl. Art. 108 OG; <ref-ruling> ff.) und nicht lediglich die Asyl- bzw. Wegweisungsverfügung in Frage stellt (vgl. das Urteil vom 10. März 2004, E. 2.2; <ref-ruling> ff.; <ref-ruling> E. 2 S. 220; <ref-ruling> E. 2), offensichtlich unbegründet und kann deshalb ohne Weiterungen im vereinfachten Verfahren nach Art. 36a OG erledigt werden:
2.1 Dass die Voraussetzungen für die Ausschaffungshaft grundsätzlich gegeben sind, hat das Bundesgericht bereits in seinem Urteil vom 10. März 2004 erkannt; es kann im Wesentlichen auf die entsprechenden Ausführungen verwiesen werden. Der Beschwerdeführer ist am 21. Oktober 2003 im Asylverfahren rechtskräftig aus der Schweiz weggewiesen worden. Er hat hernach wiederholt erklärt, nicht in seine Heimat zurückkehren zu wollen, und ist hier bei verschiedenen Ladendiebstählen angehalten worden. Nachdem seine Identität nach wie vor nicht erstellt ist und er erklärt, nicht bereit zu sein, nach Georgien zurückzukehren, bietet er auch heute noch keine Gewähr dafür, dass er sich ohne Haft zu gegebener Zeit den Behörden für den Vollzug der Wegweisung zur Verfügung halten wird (Art. 13b Abs. 1 lit. c ANAG [SR 142.20] "Untertauchensgefahr"; vgl. <ref-ruling> E. 2.1 S. 243). Trotz der behördlichen Bemühungen konnten für ihn bisher keine Reisepapiere beschafft werden. Nach Angaben der georgischen Konsulin dürfte die von ihm benutzte Identität falsch sein; es ist deshalb vorgesehen, ihn nunmehr im Juni einer georgischen Delegation vorzuführen. Solche Schwierigkeiten bei der Papierbeschaffung bilden praxisgemäss ein besonderes Hindernis im Sinne von Art. 13b Abs. 2 ANAG, welches die Verlängerung der Ausschaffungshaft rechtfertigt (<ref-ruling> E. 4.1.2). Die damit verbundenen Verzögerungen hat sich der Beschwerdeführer selber zuzuschreiben (vgl. Art. 13b Abs. 3 ANAG; <ref-ruling> E. 3a S. 51 mit Hinweisen), nachdem er bisher seinen gesetzlichen Mitwirkungspflichten nicht nachgekommen ist (vgl. Art. 13f ANAG gemäss Ziff. I/1 des Bundesgesetzes vom 19. Dezember 2003 über das Entlastungsprogramm 2003 [AS 2004 1633]). Im Moment kann nicht gesagt werden, dass es den Behörden innert absehbarer Zeit nicht doch noch gelingen wird, für ihn einen Laissez-Passer zu beschaffen; es besteht deshalb auch (noch) keine rechtliche oder tatsächliche Unmöglichkeit des Wegweisungsvollzugs im Sinne von Art. 13c Abs. 5 lit. a ANAG (vgl. <ref-ruling> E. 4.1.3).
2.2 Soweit der Beschwerdeführer geltend macht, er wolle keine georgische Abordnung treffen, da er aus Abchasien stamme und er von den georgischen Behörden verfolgt werde, setzt er sich zu seinen Aussagen vor dem Haftrichter vom 9. Februar 2004 in Widerspruch, wo er erklärt hatte, mit den Georgiern gegen die Abchasier gekämpft zu haben, weshalb er nicht nach Abchasien zurückkehren wolle. Abchasien ist kein international anerkannter souveräner Staat, sondern gehört grundsätzlich zu Georgien, weshalb die Papierbeschaffung über deren Behörden zu erfolgen hat. Zwar verspricht der Beschwerdeführer, bei einer Haftentlassung sofort nach Russland auszureisen, doch ist nicht ersichtlich, wie er dies ohne Papiere rechtmässig tun könnte. Seit dem negativen Asylentscheid bis zur Inhaftierung bestand für ihn hinreichend Gelegenheit, die Schweiz zu verlassen, doch hat er dies nicht getan.
2.2 Soweit der Beschwerdeführer geltend macht, er wolle keine georgische Abordnung treffen, da er aus Abchasien stamme und er von den georgischen Behörden verfolgt werde, setzt er sich zu seinen Aussagen vor dem Haftrichter vom 9. Februar 2004 in Widerspruch, wo er erklärt hatte, mit den Georgiern gegen die Abchasier gekämpft zu haben, weshalb er nicht nach Abchasien zurückkehren wolle. Abchasien ist kein international anerkannter souveräner Staat, sondern gehört grundsätzlich zu Georgien, weshalb die Papierbeschaffung über deren Behörden zu erfolgen hat. Zwar verspricht der Beschwerdeführer, bei einer Haftentlassung sofort nach Russland auszureisen, doch ist nicht ersichtlich, wie er dies ohne Papiere rechtmässig tun könnte. Seit dem negativen Asylentscheid bis zur Inhaftierung bestand für ihn hinreichend Gelegenheit, die Schweiz zu verlassen, doch hat er dies nicht getan.
3. 3.1 Dem Ausgang des Verfahrens entsprechend würde der unterliegende Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 OG). Es rechtfertigt sich jedoch, praxisgemäss von der Erhebung einer Gerichtsgebühr abzusehen (Art. 154 und Art. 153a OG; vgl. Urteil 2A.86/2001 vom 6. März 2001, E. 3).
3.2 Der Migrationsdienst des Kantons Bern wird ersucht, dafür besorgt zu sein, dass der vorliegende Entscheid dem Beschwerdeführer korrekt eröffnet und nötigenfalls verständlich gemacht wird.

Demnach erkennt das Bundesgericht
im Verfahren nach Art. 36a OG:
im Verfahren nach Art. 36a OG:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Es werden keine Kosten erhoben.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsdienst des Kantons Bern und dem Haftgericht III Bern-Mittelland sowie dem Bundesamt für Flüchtlinge schriftlich mitgeteilt.
Lausanne, 1. Juni 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: