Sachverhalt:
A. Die reisen.ch AG, Bern (Beschwerdeführerin), ist Inhaberin der Domain-Namen "wellnessfuehrer.ch" und "wellness-fuehrer.ch". Die für die Registrierung von Domain-Namen der Top Level Domain (TLD) "ch" zuständige SWITCH (Beschwerdegegnerin) beabsichtigte, ab 1. März 2004 die Registrierung von Domain-Namen zuzulassen, die neu auch Zeichen ausserhalb des ASCII-Zeichensatzes (z.B. "ü") enthalten könnten (sog. Internationalized Domain Names, IDN). Die Beschwerdeführerin ersuchte am 18. Januar 2004 die Beschwerdegegnerin um Verschiebung des genannten Termins. Mit dem Gesuch versuchte sie auch zu erreichen, dass die Domain-Namen "wellnessführer.ch" und "wellness-führer.ch" ihr bzw. keinen Dritten zugeteilt würden. Am 4. Februar 2004 erklärte die Beschwerdegegnerin, dass ihr in der fraglichen Angelegenheit keine Verfügungskompetenz zukomme; ausserdem sei die Verschiebung des Einführungstermins von IDN und die Vorreservierung von Domain-Namen ausgeschlossen.
B. Am 15. Februar 2004 gelangte die Beschwerdeführerin an das Bundesamt für Kommunikation (BAKOM). Sie verlangte die Aufhebung der "Verfügung" der Beschwerdegegnerin vom 4. Februar 2004, die Zuteilung der genannten Domain-Namen und die Verschiebung des Zuteilungstermins. Das BAKOM behandelte die Eingabe als Aufsichtsbeschwerde und wies sie am 24. Februar 2004 ab. Das BAKOM bestätigte die Auffassung der Beschwerdegegnerin, wonach dieser keine Verfügungskompetenz zustehe; diese handle gegenüber ihrer Kundschaft rein privatrechtlich; die Zuteilung von Domain-Namen werde nicht durch das öffentliche Bundesrecht, sondern privatrechtlich geregelt; eine Vorreservierung im Sinne der Beschwerdeführerin wäre bundesrechtswidrig.
In der dagegen erhobenen Beschwerde an die Eidgenössische Rekurskommission für Infrastruktur und Umwelt (REKO INUM) vom 27. Februar 2004 beantragte die Beschwerdeführerin die Aufhebung des von ihr als Verfügung bezeichneten Schreibens des BAKOM vom 24. Februar 2004; ausserdem verlangte sie, es seien ihr die Domain-Namen "wellnessführer.ch" und "wellness-führer.ch" zuzuteilen; eventuell sei festzustellen, dass diese Namen Dritten nicht zugeteilt werden dürfen und der Zuteilungstermin vom 1. März 2004 zu verschieben sei.
Mit Entscheid vom 16. September 2004 trat die REKO INUM auf die gegen das Schreiben des BAKOM vom 24. Februar 2004 gerichtete Beschwerde nicht ein, soweit das Verfahren nicht wegen Gegenstandslosigkeit abgeschrieben wurde. Die Rekurskommission hielt zunächst fest, die Beschwerdeführerin habe ihre Rechtsbegehren erweitert, worauf auch dann nicht einzutreten wäre, wenn eine Verfügung angefochten wäre; sie schloss, dass es an einem durch Verfügung zu regelnden Gegenstand fehle; denn aus der gestützt auf Art. 28 Abs. 2 des Fernmeldegesetzes (FMG, SR 784.10) erlassenen Verordnung über die Adressierungselemente im Fernmeldebereich (AEFV, SR 784.104) sowie aus den vom BAKOM erlassenen technischen und administrativen Vorschriften (SR 784.101.113/2.13) ergebe sich, dass die Beschwerdegegnerin als Registerbetreiberin das Verhältnis zwischen ihr und den Inhabern sowie weiteren an der Zuteilung und Verwaltung von Domain-Namen beteiligten Personen durch privatrechtlichen Vertrag regle.
C. Mit Eingabe vom 10. Oktober 2004 stellt die Beschwerdeführerin folgende Rechtsbegehren: Der Entscheid der Rekurskommission vom 16. September 2004 sei aufzuheben und die Sache sei zur materiellen Beurteilung an die zuständige Vorinstanz zurückzuweisen. Sie rügt, die Rekurskommission habe Art. 5 und 44 VwVG sowie das Gesetzmässigkeitsprinzip verletzt, indem sie den Verfügungscharakter des Entscheids verneint habe, mit dem das Gesuch um Zuteilung eines Domain-Namens mit der Endung "ch" abgewiesen worden sei. Weiter rügt die Beschwerdeführerin, der Beschwerdegegnerin sei in Verletzung von Art. 6, 48 und 64 VwVG eine Parteientschädigung zugesprochen worden.

Das Bundesgericht zieht in Erwägung:
1. Das Bundesgericht beurteilt nach Art. 97 Abs. 1 OG letztinstanzlich Verwaltungsgerichtsbeschwerden gegen Verfügungen im Sinne von <ref-law>, insbesondere auch Verfügungen der eidgenössischen Rekurskommissionen (Art. 98 lit. e OG). Die Beschwerdeführerin, auf deren Rechtsmittel die Vorinstanz nicht eintrat, hat ein schutzwürdiges Interesse an der Prüfung, ob von der Durchführung eines Verwaltungsverfahrens abgesehen werden durfte (<ref-ruling> E. 1 mit Hinweisen). Es liegt kein Ausschlussgrund im Sinne von Art. 99 ff. OG vor. Die formellen Anforderungen sind erfüllt. Auf die Beschwerde ist daher einzutreten. Zu prüfen ist, ob die Vorinstanz Bundesrecht verletzt hat, indem sie die Weigerung der Beschwerdegegnerin geschützt hat, über das Gesuch der Beschwerdeführerin durch Verfügung zu entscheiden.
2. Das Fernmeldegesetz (FMG) regelt in den Art. 28 bis 30 die Adressierungselemente. Deren Verwaltung und Zuteilung ist in <ref-law> geregelt. Nach Absatz 1 dieser Bestimmung verwaltet das Bundesamt die Adressierungselemente unter Beachtung der internationalen Normen. Gemäss Absatz 2 kann das Bundesamt die Verwaltung und Zuteilung bestimmter Adressierungselemente Dritten übertragen. Der Bundesrat regelt die Einzelheiten, namentlich die Aufsicht durch das Bundesamt. Zu den Adressierungselementen gehören insbesondere die Internet Domain-Namen (Fischer/Sidler in Weber [Hrsg.], Schweizerisches Bundesverwaltungsrecht, Bd. V/1, 2. Aufl. 2003, Informations- und Kommunikationsrecht, S. 216). In der Verordnung über die Adressierungselemente im Fernmeldebereich (AEFV) hat der Bundesrat in Art. 14 bis 14i die der Domain "ch" untergeordneten Domain-Namen geregelt (vgl. AS 2002 S. 273).
2.1 Nach <ref-law> bezeichnet das Bundesamt die Registerbetreiberin und schliesst mit ihr einen verwaltungsrechtlichen Vertrag ab. Die Aufgaben und Pflichten der Betreiberin werden in Art. 14a Abs. 2 und 14b AEFV aufgeführt. Nach <ref-law> ist die Registerbetreiberin vorbehaltlich der Fälle von Nichtzahlung oder zweifelhafter Zahlungsfähigkeit verpflichtet, ihre Dienste allen Nutzerinnen und Nutzern des Internets anzubieten. Nach <ref-law> unterstellt die Betreiberin (vorbehaltlich abweichender Bestimmungen des IPRG und des LugÜ) Streitigkeiten im Zusammenhang mit der ihr übertragenen Verwaltung und Zuteilung der Domain-Namen schweizerischem Recht und der schweizerischen Gerichtsbarkeit. Nach <ref-law> legt sie die allgemeinen Geschäftsbedingungen ihres Diensteangebots fest und unterbreitet sie dem Bundesamt zur Genehmigung. Sie setzt gemäss <ref-law> die Preise für ihre Dienste auf Grund der entstandenen Kosten sowie der Notwendigkeit einen angemessenen Gewinn zu erzielen fest und unterbreitet die Preise dem Bundesamt zur Genehmigung. Nach <ref-law> schliesst die Registerbetreiberin mit der Dachorganisation für die Verwaltung der Domain-Namen auf internationaler Ebene einen Vertrag ab, der vor Unterzeichnung vom Bundesamt zu genehmigen ist. Gemäss <ref-law> teilt die Registerbetreiberin die Domain-Namen auf Gesuch und nach der Reihenfolge der Gesuchseingänge zu (Abs. 1); sie überprüft nicht, ob eine Gesuchstellerin berechtigt ist, die alphanumerischen Bezeichnungen des verlangten Domain-Namens zu verwenden, wobei Streitigkeiten über die privaten Rechte Dritter an einer solchen Bezeichnung sich nach den zivilrechtlichen Bestimmungen richten (Abs. 2). Die Registerbetreiberin wird in <ref-law> verpflichtet, einen Streitbeilegungsdienst zu schaffen (Abs. 1), dessen Organisationsstruktur und Verfahrensvorschriften der Genehmigung des Bundesamtes bedürfen (Abs. 3); die Klage bei einem Zivilrichter bleibt vorbehalten (Abs. 4).
2.2 Die Vorinstanz hat aus diesen Bestimmungen der AEFV zutreffend geschlossen, dass die Beziehungen der Registerbetreiberin mit den Nutzerinnen und Nutzern dem Privatrecht unterstehen. Die zivilrechtliche Natur des Rechtsverhältnisses ergibt sich (sinngemäss) insbesondere aus <ref-law>, sind doch das LugÜ (Übereinkommen über die gerichtliche Zuständigkeit und die Vollstreckung gerichtlicher Entscheidungen in Zivil- und Handelssachen, SR 0.275.11) und das IPRG (Bundesgesetz über das Internationale Privatrecht, SR 291) auf privatrechtliche, nicht jedoch auf verwaltungsrechtliche Streitigkeiten anwendbar (vgl. Art. 1, LugÜ, Ingress; Volken, Zürcher Kommentar zum IPRG, N. 21 vor Art. 2; Berti, Basler Kommentar, N. 35 Vorbemerkungen zu Art. 2; Volken, a.a.O., N. 18 zu Art. 2). Die Bestimmung des anwendbaren Rechts und des Gerichtsstandes ist denn auch für privatrechtliche Verträge verbreitet, erscheint dagegen für Verwaltungssachen ausgeschlossen. Mit der entsprechenden Bestimmung wird daher die privatrechtliche Natur des Rechtsverhältnisses sinngemäss vorausgesetzt. Auch sind im Privatrechtsverkehr allgemeine Geschäftsbedingungen verbreitet (vgl. dazu Kramer, Berner Kommentar, N. 271 zu Art. 19-20 OR sowie Gauch/Schluep/Schmid, Schweizerisches Obligationenrecht, Allgemeiner Teil, 8. Aufl., N. 1116 mit Hinweisen auf die Literatur). In öffentlichrechtlichen, insbesondere durch Verfügung begründeten Rechtsbeziehungen ist dagegen mindestens der Begriff der allgemeinen Geschäftsbedingungen selbst dann nicht geläufig, wenn regelmässig eine Vielzahl von Verfügungen gleicher Art erlassen werden. Auch aus <ref-law> ergibt sich insofern, dass der Bundesrat von einer privatrechtlichen Rechtsbeziehung der Registerbetreiberin zu den Nutzerinnen und Nutzern ausgeht. In der Lehre wird denn auch ohne Weiteres angenommen, dass die Beziehungen des Delegationärs bzw. der Registerbetreiberin zu den Kunden grundsätzlich dem Privatrecht unterstehen, weshalb gegen Zuteilungsentscheide mit Ausnahme der Aufsichtsbeschwerde kein verwaltungsrechtlicher Beschwerdeweg zur Verfügung steht (Fischer/Sidler, a.a.O., S. 212).
2.3 Das Bundesgericht kann im Verwaltungsgerichtsbeschwerde-Verfahren Verordnungen des Bundesrates vorfrageweise auf ihre Gesetzes- und Verfassungsmässigkeit prüfen. Bei unselbstständigen Verordnungen, die sich auf eine gesetzliche Delegation stützen, prüft es, ob sich der Bundesrat an die Grenzen der ihm im Gesetz eingeräumten Befugnisse gehalten hat. Soweit das Gesetz den Bundesrat nicht ermächtigt, von der Verfassung abzuweichen, befindet das Gericht auch über die Verfassungsmässigkeit der unselbstständigen Verordnung. Wird dem Bundesrat durch die gesetzliche Delegation ein sehr weiter Ermessensspielraum für die Regelung auf Verordnungsebene eingeräumt, so ist dieser Spielraum nach <ref-law> für das Bundesgericht verbindlich; das Gericht darf in diesem Fall bei der Prüfung der Verordnung nicht sein eigenes Ermessen an die Stelle desjenigen des Bundesrates setzen, sondern beschränkt sich auf die Prüfung, ob die Verordnung den Rahmen der dem Bundesrat im Gesetz delegierten Kompetenzen offensichtlich sprengt oder aus anderen Gründen gesetz- oder verfassungswidrig ist (<ref-ruling> E. 3b; <ref-ruling> E. 3a mit Hinweisen). Es kann dabei namentlich prüfen, ob sich eine Verordnungsbestimmung auf ernsthafte Gründe stützen lässt oder ob sie <ref-law> widerspricht, weil sie sinn- und zwecklos ist, rechtliche Unterscheidungen trifft, für die ein vernünftiger Grund in den tatsächlichen Verhältnissen nicht ersichtlich ist, oder Unterscheidungen unterlässt, die richtigerweise hätten getroffen werden müssen. Für die Zweckmässigkeit der angeordneten Massnahmen trägt demgegenüber der Bundesrat die Verantwortung (<ref-ruling> E. 2.3; <ref-ruling> E. 3b, je mit Hinweisen).
2.4 <ref-law> ermächtigt das Bundesamt zur Übertragung einzelner Adressierungselemente an Dritte und den Bundesrat zur Regelung der Einzelheiten. Die Beschwerdeführerin stellt grundsätzlich nicht in Frage, dass die Verwaltung und Zuteilung von Domain-Namen rechtmässig auf die Beschwerdegegnerin übertragen wurde. Sie hält jedoch dafür, <ref-law> erkläre diese Dienstleistung ausdrücklich zur Verwaltungsaufgabe des Bundes und mit der Übertragung dieser Aufgabe an die Beschwerdegegnerin sei dieser auch die Kompetenz übertragen worden, die Zuteilung der Domain-Namen an Private mittels Verfügung vorzunehmen; die Beschwerdegegnerin wäre nach Ansicht der Beschwerdeführerin zur privatrechtlichen Gestaltung ihrer Beziehungen zu den Benutzern nur befugt, wenn dies im (formellen) Gesetz ausdrücklich so vorgesehen wäre. Sie verkennt damit, dass sich die Wahl der zulässigen Handlungsformen der Verwaltung auch sinngemäss aus dem Gesetz ergeben kann (vgl. <ref-ruling> E. 4b; Moor, Droit administratif Bd. II 2. Aufl. 2002 S. 370 ff; Häfelin/Müller, Allgemeines Verwaltungsrecht, 4. Aufl. 2002, S. 315 N. 1530, S. 59 N. 285 f). Das Verhältnis zu den Benutzern kann insbesondere dann, wenn nicht eigentlich hoheitliche, sondern gewerbliche Tätigkeiten in Frage stehen, durchaus privatrechtlich geregelt werden (Tschannen/ Zimmerli, a.a.O., S. 356). Die Zuteilung von Domain-Namen gehört zur Leistungsverwaltung, die keines Verwaltungszwangs bedarf. Sie wurde vor Erlass des geltenden FMG durch privatrechtlichen Vertrag geregelt, wie die Beschwerdeführerin selbst bemerkt. Das geltende FMG hat daran insoweit nichts geändert. Die Delegationsnorm wurde, wie aus dem Votum des Berichterstatters im Ständerat hervorgeht, erlassen, um bestehende, gut funktionierende Systeme wie beim Telex oder im Internet bei den Domain-Namen nicht wieder rückgängig zu machen und dem BAKOM übertragen zu müssen (AB 1997 S S. 95). Die Beschwerdeführerin behauptet das Gegenteil, vermag jedoch keine Gründe zu nennen, weshalb entgegen der Einschätzung des Gesetzgebers das historisch gewachsene System nicht mehr zu befriedigen vermocht habe. Der historische gesetzgeberische Wille war darauf gerichtet, das bestehende System der Adressierungselemente im Internet zu erhalten, das sich in privater Initiative weltweit entwickelt hatte (vgl. Fischer/Sidler, a.a.O., S. 212/216). Der Bundesrat hat den Rahmen der Ermächtigung gemäss <ref-law> nicht überschritten, wenn er bestimmte, dass die Registerbetreiberin den Nutzerinnen und Nutzern wie bis anhin die Domain-Namen durch privatrechtlichen Vertrag übertrage. Es sind auch keine Gründe ersichtlich, welche einer derartigen Regelung von Verfassungs wegen entgegen stehen könnten.
3. Die Beschwerdeführerin rügt, die Vorinstanz habe Art. 6, 48 und 64 VwVG verletzt, indem sie der anwaltlich vertretenen Beschwerdegegnerin eine Parteientschädigung zugesprochen habe.
3.1 Als Parteien gelten gemäss <ref-law> Personen, deren Rechte oder Pflichten die Verfügung berühren soll, und andere Personen, Organisationen oder Behörden, denen ein Rechtsmittel gegen die Verfügung zusteht. Da die Beschwerdegegnerin entgegen der Ansicht der Beschwerdeführerin ihre Beziehungen zu den Internet-Nutzerinnen und Nutzern privatrechtlich regelt, ist sie nicht Vorinstanz im Sinne dieser Bestimmung. Sie ist jedoch vom Ausgang des vorliegenden Verfahrens betroffen, da sie - falls die Rechtsauffassung der Beschwerdeführerin zutreffen würde - organisatorische Umstellungen vornehmen müsste. Somit ist sie von der Vorinstanz zu Recht als Partei im Sinne von <ref-law> qualifiziert worden.
3.2 Nach <ref-law> kann die Beschwerdeinstanz der ganz oder teilweise obsiegenden Partei von Amtes wegen oder auf Begehren eine Entschädigung für ihr erwachsene notwendige und verhältnismässig hohe Kosten zusprechen. Die Beschwerdeführerin bestreitet nicht, dass die Beschwerdegegnerin mit ihren Anträgen vor der Vorinstanz durchgedrungen ist und damit im Verfahren obsiegt hat. Sie bestreitet auch nicht grundsätzlich, dass die Komplexität der Sache den Beizug einer rechtskundigen Vertreterin erforderte. Die Voraussetzungen für die Entschädigung nach <ref-law> sind damit gegeben. Dass die Beschwerdegegnerin über einen internen Rechtsdienst verfüge, den sie mit der Stellungnahme hätte betrauen können, ändert daran nichts. Soweit damit sinngemäss geltend gemacht werden sollte, die Parteikosten wären geringer ausgefallen, wenn die Beschwerdegegnerin eigene Angestellte beigezogen hätte, fehlt dafür jede Begründung.
4. Die Vorinstanz ist zu Recht auf die Beschwerde vom 27. Februar 2004 nicht eingetreten. Die vorliegende Verwaltungsgerichtsbeschwerde gegen diesen Nichteintretensentscheid ist daher abzuweisen. Bei diesem Ausgang des Verfahrens hat die Beschwerdeführerin die Verfahrenskosten zu tragen (Art. 156 Abs. 1 OG). Sie hat der anwaltlich vertretenen privaten Beschwerdegegnerin überdies eine Parteientschädigung zu leisten (Art. 159 Abs. 2 OG). Von der in dieser Bestimmung genannten Regel ist insbesondere deshalb abzusehen, weil die Beschwerdegegnerin keine Verfügungen erlässt (vgl. <ref-ruling> E. 8 S. 62).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 3'000.-- wird der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und der Eidgenössischen Rekurskommission für Infrastruktur und Umwelt sowie dem Eidgenössischen Departement für Umwelt, Verkehr, Energie und Kommunikation (UVEK) schriftlich mitgeteilt.
Lausanne, 28. Januar 2005
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: