Sachverhalt:
A. X._ (geb. 1977) stammt aus Uganda. Er durchlief in der Schweiz erfolglos ein Asylverfahren und wurde rechtskräftig aus der Schweiz weggewiesen. Da er nicht bereit war, bei der Beschaffung seiner Papiere mitzuwirken, nahm ihn das Kantonale Ausländeramt St. Gallen am 4. Juni 2008 in Durchsetzungshaft. Diese wurde wiederholt verlängert, letztmals am 27./29. April 2009 bis zum 3. Juli 2009. X._ ist hiergegen am 14. Mai 2009 mit dem Antrag an die Verwaltungsrekurskommission des Kantons St. Gallen gelangt, den Entscheid ihres Einzelrichters vom 29. April 2009 "zurückzuweisen".
B. Die Verwaltungsrekurskommission des Kantons St. Gallen überwies am 29. Mai 2009 die Eingabe als Beschwerde gegen den Haftverlängerungsentscheid an das Bundesgericht. X._ habe innert der ihm gesetzten Frist keine mündliche Verhandlung verlangt, weshalb sein Schreiben gegebenenfalls als Beschwerde in die Zuständigkeit des Bundesgerichts falle. Mit Verfügung vom 4. Juni 2009 leitete der Abteilungspräsident den Schriftenwechsel ein, wobei er darauf hinwies, dass sich nach <ref-ruling> ff. "insbesondere die Frage" stelle, ob die Verwaltungsrekurskommission des Kantons St. Gallen als oberes Gericht im Sinne von Art. 86 Abs. 2 BGG gelten könne.
C. Das Verwaltungsgericht des Kantons St.Gallen beantragte am 8. Juni 2009 unter Hinweis auf die verfassungsrechtliche Organisationsautonomie der Kantone (Art. 47 Abs. 2 [in der Fassung vom 28. November 2004] und Art. 52 Abs. 1 BV), die Verwaltungsrekurskommission als oberes kantonales Gericht im Sinne von Art. 86 Abs. 2 BGG zu anerkennen. Die Verwaltungsrekurskommission hat sich am 9. Juni 2009 den entsprechenden Ausführungen angeschlossen und darauf hingewiesen, dass andere bundesgerichtliche Abteilungen Beschwerden in Bereichen, in denen das kantonale Recht ebenfalls die Verwaltungsrekurskommission als letzte Instanz bezeichne, an die Hand genommen hätten. Das Bundesamt für Migration hat darauf verzichtet, sich vernehmen zu lassen. Das Kantonale Ausländeramt St. Gallen beantragt, die "Verwaltungsgerichtsbeschwerde" abzuweisen. X._ hat am 17./19. Juni 2009 an seinem (sinngemässen) Antrag festgehalten, er sei aus der Durchsetzungshaft zu entlassen.

Erwägungen:
1. 1.1 Das Bundesgericht prüft seine Zuständigkeit und die Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (Art. 29 Abs. 1 BGG; <ref-ruling> E. 1 mit Hinweisen). Gegen kantonale richterliche Entscheide betreffend die Zwangsmassnahmen im Ausländerrecht steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen, falls sie sich gegen den Entscheid einer Behörde im Sinne von Art. 86 BGG richtet. Danach haben die Kantone als unmittelbare Vorinstanzen des Bundesgerichts obere Gerichte einzusetzen, soweit "nicht nach einem anderen Bundesgesetz Entscheide anderer richterlicher Behörden der Beschwerde an das Bundesgericht unterliegen". Nach Art. 130 Abs. 3 BGG müssen die Kantone innert zwei Jahren nach Inkrafttreten des Bundesgerichtsgesetzes unter anderem Ausführungsbestimmungen über die Zuständigkeit, die Organisation und das Verfahren der Vorinstanzen im Sinne von Art. 86 Abs. 2 und 3 BGG erlassen. Bis zu diesem Zeitpunkt können sie die Ausführungsbestimmungen nötigenfalls und vorläufig in die Form nicht referendumspflichtiger Erlasse kleiden (vgl. Art. 130 Abs. 4 BGG). Am 31. Dezember 2008 ist die Frist für die Anpassung der kantonalen Gesetzgebung abgelaufen.
1.2 Das Bundesgericht hat sich in <ref-ruling> ff. unter Berücksichtigung der Doktrin und der Rechtsprechung (<ref-ruling> E. 4.4 S. 323 f.) eingehend mit den sich im Bereich der Zwangsmassnahmen im Ausländerrecht aus Art. 86 Abs. 2 BGG ergebenden Konsequenzen befasst: Als unmittelbare kantonale Vorinstanzen des Bundesgerichts kommen sowohl die höchsten kantonalen Gerichte in Verwaltungs-, Zivil- oder Strafsachen als auch verwaltungsunabhängige besondere Justizbehörden in Frage. Ein doppelter Instanzenzug ist nicht nötig; genausowenig muss ein einheitliches Gericht für sämtliche öffentlich-rechtlichen Materien bezeichnet werden. Das Bundesrecht schliesst besonders geeignete Spezialgerichtsbehörden wie ein Haftgericht als Vorinstanzen somit nicht aus. Hingegen verlangt das Erfordernis des "oberen" Gerichts, dass die entsprechende Justizbehörde für das ganze Kantonsgebiet zuständig und hierarchisch keiner anderen Gerichtsinstanz unterstellt ist (<ref-ruling> E. 4.1; <ref-ruling> E. 3.5 S. 135). Diese Voraussetzung ist nicht erfüllt, wenn gegen ihre Entscheide ein ordentlicher Beschwerdeweg an eine andere kantonale Instanz offen steht. Dabei ist nicht nur ausschlaggebend, dass die Gerichtsbehörde im gerade fraglichen Sachbereich letztinstanzlich entscheidet, sondern dass ihre Entscheide ganz allgemein, also auch in ihren übrigen Zuständigkeitsbereichen, nicht an eine höhere kantonale Instanz weitergezogen werden können (<ref-ruling> E. 4.1 S. 98 unter Hinweis auf PIERRE MOOR, De l'accès au juge et de l'unification des recours, in: Bellanger/Tanquerel [Hrsg.], Les nouveaux recours fédéraux en droit public, 2006, S. 168; vgl. auch ALAIN WURZBURGER, in: Corboz und andere, Commentaire de la LTF, 2009, N. 22 zu Art. 86 BGG; MARTIN BUSINGER, Die Anforderungen von Art. 86 Abs. 2 BGG an letzte kantonale Gerichtsinstanzen im Bereich der ausländerrechtlichen Haft, in: Jusletter 2. März 2009, Rz. 11). Ob die erforderliche hierarchische Unabhängigkeit auch bereits dann fehlt, wenn eine Spezialjustizbehörde der Aufsicht eines anderen kantonalen Gerichts untersteht, ohne dass gegen ihre Entscheide ein kantonales Rechtsmittel ergriffen werden kann, bezeichnete das Bundesgericht in <ref-ruling> ff. als "fraglich" (E. 4.1 S. 98 f.), ohne die Problematik abschliessend zu beurteilen.
2. 2.1 Aufgrund dieser Vorgaben kann gegen den beanstandeten Haftverlängerungsentscheid der Verwaltungsrekurskommission St. Gallen nicht an das Bundesgericht gelangt werden: Zwar richtet sich der Rechtsschutz bei den ausländerrechtlichen Zwangsmassnahmen gemäss Art. 93ter des Gesetzes vom 16. Mai 1965 über die Verwaltungsrechtspflege (VRPG/SG; sGS 951.1) "sachgemäss nach den Vorschriften über den Rekurs", wobei der hauptamtliche Richter oder das Mitglied der Verwaltungsrekurskommission "oberes Gericht" und die Beschwerde an das Verwaltungsgericht "unzulässig" ist, doch können die Entscheide der Verwaltungsrekurskommission auf zahlreichen anderen Gebieten kantonsintern an das Verwaltungsgericht weitergezogen werden (vgl. Art. 59 ff. VRPG/SG). Dieses übt zudem nach Art. 43 des Gerichtsgesetzes vom 2. April 1987 (sGS 941.1) die administrative Aufsicht über die Verwaltungsrekurskommission als ihm unterstelltes Gericht aus. Die Verwaltungsrekurskommission nimmt somit - wie das in <ref-ruling> ff. beurteilte Haftgericht III Bern-Mittelland - nur in einzelnen Sachbereichen letztinstanzliche Entscheidkompetenzen wahr, weshalb ihm - unabhängig von der aufsichtsrechtlichen Organisation - nicht die Stellung eines oberen kantonalen Gerichts nach Art. 86 Abs. 2 erster Halbsatz BGG zukommt.
2.2 Was die kantonalen Behörden hiergegen einwenden, ist nicht geeignet, die mit <ref-ruling> ff. eingeleitete Praxis in Frage zu stellen und die St. Galler Regelung anders zu beurteilen als diejenige des Kantons Bern:
2.2.1 Soweit das Verwaltungsgericht des Kantons St. Gallen darauf hinweist, dass die Verwaltungsrekurskommission nicht wie das Haftgericht III Bern-Mittelland eine regionale Behörde sei, verkennt es, dass dieses hinsichtlich der Zwangsmassnahmen im Kanton Bern ebenfalls für das ganze Kantonsgebiet zuständig erklärt worden war. Nach Art. 46 Abs. 2 BV belässt der Bund den Kantonen zwar "möglichst grosse Gestaltungsfreiheit", zudem trägt er "den kantonalen Besonderheiten Rechnung"; dies hindert den Bundesgesetzgeber indessen nicht daran, einheitliche Vorgaben festzulegen und durch geeignete Vorkehren für deren Durchsetzung zu sorgen: Nach Art. 188 Abs. 2 BV bestimmt das (Bundes-)Gesetz die Organisation und das Verfahren des Bundesgerichts. Hauptziel der Justizreform war die Sicherung von dessen Funktionsfähigkeit als nationales Höchstgericht sowie die Vereinfachung und Stärkung des Rechtsschutzes auf allen Ebenen (statt vieler: GIOVANNI BIAGGINI, BV, Kommentar, 2007, N. 13 Vorbem. Art. 188-191c BV). Der Begriff der "oberen Gerichte" in Art. 86 Abs. 2 BGG ist bundesrechtlicher Natur; nur soweit er den Kantonen Freiräume zugesteht, können diese sich auf ihre Organisationsautonomie berufen. Sie sind nicht befugt, ihre bisher erstinstanzlich zuständigen Zwangsmassnahmengerichte zu einem in diesem Bereich "oberen" kantonalen Gericht umzugestalten, indem sie deren Entscheide einfach von einem an sich bestehenden kantonalen Rechtsmittelweg punktuell ausnehmen; nur wenn das zuständige kantonale (erstinstanzliche) Gericht bereits ein solches im Sinne von Art. 86 Abs. 2 BGG ist, kann direkt gegen dessen Entscheide an das Bundesgericht gelangt werden.
2.2.2 Falls andere Abteilungen des Bundesgerichts (implizit) abweichend entschieden haben sollten, kann der Kanton St. Gallen hieraus nichts zu seinen Gunsten ableiten: Die Frage der Letztinstanzlichkeit des angefochtenen Entscheids wurde dort - soweit ersichtlich - jeweils nicht thematisiert; überdies sind die entsprechenden Verfahren offenbar teilweise zurzeit noch hängig, oder sie sind im vereinfachten Verfahren erledigt worden. Zwar wurde die Verwaltungsrekurskommission im vorliegenden Fall ausdrücklich aufgefordert, zur entsprechenden Frage (noch) Stellung zu nehmen; es stand ihr indessen in den anderen Verfahren ebenfalls frei, sich zu dieser Frage zu äussern. Auch andere Kantone haben nach Erlass von <ref-ruling> ff. ihre Gerichtsorganisation überprüfen müssen. Dabei stehen verschiedene Möglichkeiten offen: Der Kanton kann ein gänzlich unabhängiges Haftgericht als oberes Gericht für die ausländerrechtliche Administrativhaft schaffen oder gegen die Hafturteile des bisherigen Haftgerichts die Beschwerde an das Obergericht oder das Verwaltungsgericht zulassen. Diesbezüglich steht es dem Bundesgericht nicht zu, eine Regelung vorzugeben und insofern in die kantonale Organisationsautonomie einzugreifen (vgl. <ref-ruling> E. 6.3).
2.2.2 Falls andere Abteilungen des Bundesgerichts (implizit) abweichend entschieden haben sollten, kann der Kanton St. Gallen hieraus nichts zu seinen Gunsten ableiten: Die Frage der Letztinstanzlichkeit des angefochtenen Entscheids wurde dort - soweit ersichtlich - jeweils nicht thematisiert; überdies sind die entsprechenden Verfahren offenbar teilweise zurzeit noch hängig, oder sie sind im vereinfachten Verfahren erledigt worden. Zwar wurde die Verwaltungsrekurskommission im vorliegenden Fall ausdrücklich aufgefordert, zur entsprechenden Frage (noch) Stellung zu nehmen; es stand ihr indessen in den anderen Verfahren ebenfalls frei, sich zu dieser Frage zu äussern. Auch andere Kantone haben nach Erlass von <ref-ruling> ff. ihre Gerichtsorganisation überprüfen müssen. Dabei stehen verschiedene Möglichkeiten offen: Der Kanton kann ein gänzlich unabhängiges Haftgericht als oberes Gericht für die ausländerrechtliche Administrativhaft schaffen oder gegen die Hafturteile des bisherigen Haftgerichts die Beschwerde an das Obergericht oder das Verwaltungsgericht zulassen. Diesbezüglich steht es dem Bundesgericht nicht zu, eine Regelung vorzugeben und insofern in die kantonale Organisationsautonomie einzugreifen (vgl. <ref-ruling> E. 6.3).
2.3 2.3.1 Auf die von der Verwaltungsrekurskommission dem Bundesgericht übermittelte Eingabe ist somit nicht einzutreten, und die Sache ist zur weiteren Behandlung an das Verwaltungsgericht als ordentliche obere kantonale Beschwerdeinstanz bzw. als Aufsichtsbehörde über die Verwaltungsrekurskommission zu überweisen. Dieses wird eine vorsorgliche Regelung für die bereits hängigen Fälle zu treffen haben (<ref-ruling> E. 6.3 S. 103). Im Übrigen wird der Kanton St. Gallen seine Gesetzgebung im Sinne des vorliegenden Entscheids anpassen müssen, weshalb eine Kopie von diesem auch dem Sicherheits- und Justizdepartement des Kantons St. Gallen zuzustellen ist.
2.3.2 Da die Haftverlängerung des Beschwerdeführers erstinstanzlich gerichtlich geprüft worden ist, rechtfertigt es sich nicht, ihn sofort aus der Haft zu entlassen. Die Behörden des Kantons St. Gallen haben indessen umgehend dafür zu sorgen, dass den bundesgesetzlichen Anforderungen an die kantonale Gerichtsorganisation in seinem Fall derart nachgekommen wird, dass das weitere Verfahren keine unnötige Verzögerung erfährt (<ref-ruling> E. 6.4 S. 104). Das Verwaltungsgericht des Kantons St. Gallen wird zudem ersucht, das Bundesgericht mit Blick auf künftige Beschwerdeeingänge möglichst rasch über die getroffene Lösung zu informieren.
2.3.3 Für das vorliegende Verfahren sind keine Kosten und Entschädigungen geschuldet (vgl. Art. 66 und Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten und die Sache wird an das Verwaltungsgericht des Kantons St. Gallen zur weiteren Behandlung im Sinne der Erwägungen überwiesen.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird dem Beschwerdeführer, dem Kantonalen Ausländeramt St. Gallen, dem Verwaltungsgericht, der Verwaltungsrekurskommission sowie dem Sicherheits- und Justizdepartement des Kantons St. Gallen und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. Juni 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Hugi Yar