Sachverhalt:
A. B._, wohnhaft im Kanton St. Gallen, war bei der Visana gesetzlich für Krankenpflege versichert. Vom 15. Dezember 2003 bis 28. Februar 2004 hielt sie sich nach einem Gehirnschlag mit halbseitiger Lähmung zu einer stationären Neuro-Rehabilitationsbehandlung in der allgemeinen Abteilung der in Appenzell Ausserrhoden gelegenen Rheinburg-Klinik Walzenhausen auf. Die Visana erteilte der Klinik Kostengutsprache über Fr. 220.- pro Tag mit dem Vermerk "analog dem Tarif der Rehabilitationsklinik Walenstadtberg". Die Klinik stellte B._ einen Tagesansatz von Fr. 580.- in Rechnung. Diese teilte der Visana mit, sie sei nicht bereit, eine Vergütung von lediglich Fr. 220.- pro Tag zu akzeptieren, und ersuchte um die Übernahme der gesamten fakturierten Kosten. Mit Verfügung vom 26. Mai 2004 beschränkte die Visana ihre Vergütung, da die Behandlung ohne weiteres auch in der st. gallischen Rehabilitationsklinik Walenstadtberg hätte durchgeführt werden können, auf die betreffende Tagespauschale von Fr. 220.- abzüglich der Kostenbeteiligung. Sie bestätigte dies mit Einspracheentscheid vom 18. November 2004.
B. B._ liess Beschwerde beim Versicherungsgericht des Kantons St. Gallen erheben und beantragen, die Visana sei zu verpflichten, ihr für den Aufenthalt in der Rheinburg-Klinik pro Tag Fr. 580.- zu vergüten; eventualiter sei wenigstens der Tarif zu übernehmen, der beim Aufenthalt im st. gallischen Rheuma- und Rehabilitationszentrum Klinik Valens zu bezahlen gewesen wäre. Das kantonale Gericht hiess die Beschwerde teilweise gut; es verpflichtete die Visana, der Versicherten für den stationären Aufenthalt in der Rheinburg-Klinik die Tagespauschale der Klinik Valens von Fr. 499.- (resp. Fr. 541.- ab 1. Januar 2004) zu vergüten.
C. Die Visana führt Verwaltungsgerichtsbeschwerde. Sie beantragt, der vorinstanzliche Entscheid sei insoweit aufzuheben, als sie verpflichtet werde, die Leistungen für den Aufenthalt in der Rheinburg-Klinik nach der tarifvertraglich vereinbarten Tagespauschale der Klinik Valens zu vergüten, und nicht nach derjenigen der Klinik Walenstadtberg.
B._ beantragt Abweisung der Verwaltungsgerichtsbeschwerde; die Visana sei zu verpflichten, ihr für den Aufenthalt in der Rheinburg-Klinik pro Tag Fr. 602.- zu vergüten, eventualiter aber mindestens das, was sie bei einem stationären Rehabilitationsaufenthalt in der Klinik Valens zu bezahlen gehabt hätte. Vorinstanz und Bundesamt für Gesundheit verzichten auf Vernehmlassung.
D. Am 20. Dezember 2006 hat das Eidgenössische Versicherungsgericht eine parteiöffentliche Beratung durchgeführt.
Das Eidg. Versicherungsgericht zieht in Erwägung:
1. 1.1 Gemäss Art. 129 Abs. 1 lit. b OG ist die Verwaltungsgerichtsbeschwerde unzulässig gegen Verfügungen über Tarife. Nach der Rechtsprechung ist die Verwaltungsgerichtsbeschwerde allerdings nur unzulässig gegen Verfügungen, welche den Erlass oder die Genehmigung eines Tarifs als Ganzes zum Gegenstand haben oder wenn unmittelbar einzelne Tarifbestimmungen als solche angefochten werden. Entscheidend dafür ist, dass die Gesichtspunkte, welche der Strukturierung eines Tarifs zu Grunde liegen, als nicht oder schwer justiziabel betrachtet werden. Hingegen steht die Verwaltungsgerichtsbeschwerde offen gegen Verfügungen, welche in Anwendung eines Tarifs im Einzelfall ergangen sind; dabei kann das Gericht zwar nicht den Tarif als Ganzes mit all seinen Positionen und in ihrem gegenseitigen Verhältnis auf die Gesetzmässigkeit hin überprüfen, wohl aber kann es die konkret angewandte Tarifposition ausser Acht lassen, wenn sie sich als gesetzwidrig erweist (BGE 131 V 136 Erw. 2.1 mit Hinweisen).
1.2 Im vorliegenden Verfahren geht es nicht um eine Tarifstreitigkeit im Sinne von Art. 129 Abs. 1 lit. b OG, sondern um die Anwendung eines Tarifes im Einzelfall. Streitig und zu prüfen ist, nach welchem Tarif die von der Rheinburg-Klinik gegenüber der Beschwerdegegnerin erbrachten Leistungen aus der sozialen Krankenversicherung zu vergüten sind. Unter diesem Gesichtspunkt ist auf die Verwaltungsgerichtsbeschwerde einzutreten.
2. 2.1 Die Beschwerdegegnerin beantragt, die Visana habe ihr für den Aufenthalt in der Rheinburg-Klinik anstatt der vorinstanzlich geforderten Fr. 580.- neu pro Tag Fr. 602.- zu vergüten, denn der Bundesrat habe mit Beschwerdeentscheid vom 19. Oktober 2005 die Tagespauschale der Rheinburg-Klinik rückwirkend ab 1. April 2003 auf Fr. 602.- festgesetzt, und damit den Tarif korrigiert, an den sie sich bisher mit ihrer Forderung gehalten habe.
2.2 Da das Bundesrechtspflegegesetz (OG) eine Anschlussbeschwerde nicht vorsieht, kann die Beschwerdegegnerin, die den vorinstanzlichen Entscheid nicht mit Verwaltungsgerichtsbeschwerde angefochten hat, in der letztinstanzlichen Vernehmlassung kein selbstständiges Begehren mehr im Sinne eines Antrages stellen, der über den durch die Verwaltungsgerichtsbeschwerde bestimmten Streitgegenstand hinausgeht (BGE 122 V 244 Erw. 2a, 117 V 295 Erw. 2a, 112 V 99 Erw. 1a, 110 V 51 Erw. 3c mit Hinweisen; vgl. auch BGE 122 V 36 Erw. 2a). Nach Art. 132 lit. c OG kann das Eidgenössische Versicherungsgericht aber über die Begehren der Parteien zu deren Gunsten oder Ungunsten hinausgehen; vor diesem Hintergrund sind auch die von einer Beschwerdegegnerschaft in der Vernehmlassung gestellten Anträge bzw. die damit geäusserte Rechtsauffassung überprüfbar, soweit sich der Antrag innerhalb des Streitgegenstandes und innerhalb der dem Gericht zustehenden Kognition bewegt. Wie sich aus dem Nachstehenden ergibt, erübrigt sich hier aber eine nähere Erörterung der damit aufgeworfenen Fragen.
3. 3.1 Die Kostenübernahme bei stationärer Behandlung im Rahmen der obligatorischen Krankenpflegeversicherung ist in Art. 41 KVG geregelt. Danach können die Versicherten unter den zugelassenen Leistungserbringern, die für die Behandlung ihrer Krankheit geeignet sind, frei wählen. Der Versicherer muss die Kosten höchstens nach dem Tarif übernehmen, der im Wohnkanton der versicherten Person gilt (Abs. 1 dritter Satz). Beanspruchen Versicherte aus medizinischen Gründen einen anderen Leistungserbringer, so richtet sich die Kostenübernahme nach dem Tarif, der für diesen Leistungserbringer gilt (Abs. 2). Medizinische Gründe liegen bei einem Notfall vor oder wenn die erforderlichen Leistungen im Wohnkanton oder in einem auf der Spitalliste des Wohnkantons nach Artikel 39 Absatz 1 Buchstabe e KVG aufgeführten ausserkantonalen Spital nicht angeboten werden (Abs. 2 lit. b). Beansprucht die versicherte Person aus medizinischen Gründen die Dienste eines ausserhalb ihres Wohnkantons befindlichen öffentlichen oder öffentlich subventionierten Spitals, so übernimmt der Wohnkanton die Differenz zwischen den in Rechnung gestellten Kosten und den Tarifen des betreffenden Spitals für Einwohner und Einwohnerinnen des Kantons (Abs. 3 erster Satz; Ausgleichs- oder Differenzzahlungspflicht: BGE 130 V 218, 123 V 290 und 310).
3.2 Nach BGE 127 V 145 f. Erw. 4d zeigen Wortlaut, Systematik und Entstehungsgeschichte zu Art. 41 KVG, dass die Revision des Krankenversicherungsrechts an der altrechtlichen Konzeption der grundsätzlich freien Wahl der Heilanstalt resp. des Leistungserbringers "Spital" bei allenfalls masslich beschränkter Versicherungsdeckung, soweit nicht medizinische Gründe einen bestimmten ausserkantonalen Behandlungsort erfordern, nichts geändert hat (ausführlich zum früheren Recht: BGE 127 V 143 Erw. 4c/aa-bb; vgl. auch BGE 125 V 452 f. Erw. 3a mit Hinweisen auf die Lehre). Neu ist im Wesentlichen einzig, dass im Unterschied zu früher einheitlich der Wohnkanton der versicherten Person als räumlicher Bereich mit voller Kostenübernahme durch die obligatorische Krankenpflegeversicherung gilt, sowie die Differenzzahlungspflicht der Kantone im Rahmen von Art. 41 Abs. 3 KVG. Diese Neuerungen bieten indessen nicht Anlass, den Begriff der medizinischen Gründe gemäss Art. 41 Abs. 2 (Satz 2) lit. b KVG grundsätzlich anders zu interpretieren als im Rahmen des Art. 19bis Abs. 5 KUVG. Daran ändert die Zielsetzung des Art. 41 Abs. 3 KVG (Lastenausgleich zwischen Kantonen mit unterschiedlichen Spitalversorgungsgraden sowie verstärkte Koordination zwischen den Kantonen im Bereich der Spitalplanung [BGE 123 V 297 f. Erw. 3b/aa-cc]) nichts, zumal der Gesetzgeber gleichsam folgerichtig den für die Frage medizinischer Gründe massgebenden räumlichen Bereich mit maximaler Kostendeckung um die auf der Spitalliste des Wohnkantons aufgeführten ausserkantonalen Spitäler erweitert hat (Art. 41 Abs. 1 Satz 3 und Abs. 2 lit. b KVG). Mit anderen Worten, so wenig die planerischen Elemente die aus dem Krankenversicherungsgesetz und den dazugehörigen Verordnungen sich ergebenden Ansprüche der Versicherten tangieren (BGE 125 V 454 Erw. 3b), so wenig können die medizinischen Gründe als ein zusätzliches Instrument der Spitalfinanzierung und -planung verstanden und gehandhabt werden. Desgleichen gilt in sinngemässer Übernahme der altrechtlichen Ordnung (BGE 127 V 143 f. Erw. 4c/bb), dass bei medizinisch begründeter stationärer Behandlung ausserhalb des in Art. 41 Abs. 2 lit. b KVG umschriebenen räumlichen Bereichs der Umfang der Kostenübernahme durch die obligatorische Krankenpflegeversicherung sich grundsätzlich nach dem Gebot der Wirtschaftlichkeit der Leistungen gemäss Art. 32 Abs. 1 KVG richtet.
3.3 Der Entscheid, ob ein Spital in die Spitalliste aufzunehmen sei, hat eine wesentliche gesundheits- und sozialpolitische, aber regelmässig auch regional-, beschäftigungs- und allgemeinpolitische Bedeutung. Es handelt sich dabei um einen primär politischen Entscheid. Dementsprechend gibt das Gesetz den einzelnen Spitälern keinen Rechtsanspruch auf Aufnahme in die Spitalliste; es fehlt weitgehend an rechtlichen Kriterien für den Entscheid, welche Spitäler in die Spitalliste aufzunehmen sind. Vielmehr haben die zuständigen kantonalen Behörden einen erheblichen Ermessensspielraum (BGE 132 V 12 Erw. 2.4.1 in fine mit Hinweisen auf BGE 126 V 182 Erw. 4b und 6d; Entscheid des Bundesrates vom 19. Dezember 2001 in Sachen Privatklinik P. [RKUV 2002 Nr. KV 219 S. 301 Erw. 2.1]; Eugster, Krankenversicherung, in: Schweizerisches Bundesverwaltungsrecht [SBVR], Soziale Sicherheit, Basel 1998, S. 127 f.; Mattig, Grenzen der Spitalplanung aus verfassungsrechtlicher Sicht, Zürich 2003, S. 130). Was hier vorab in Bezug auf die Spitalliste des Standortkantons ausgeführt worden ist (Staffelbach, Interkantonale Spitalplanung und Kostentragung, in: AJP 3/2006 S. 269), hat ebenso für die Aufnahme eines ausserkantonal gelegenen Spitals zu gelten.
4. Die Hospitalisation der Beschwerdegegnerin ist nicht aus medizinischen Gründen ausserhalb des Wohnkantons erfolgt, denn die erforderliche Leistung wird im Kanton St. Gallen angeboten (Art. 41 Abs. 2 lit. a KVG e contrario). Ein solcher Grund ist nach dem eben Gesagten insbesondere nicht darin zu sehen, dass die ausserrhodische Rheinburg-Klinik eine im Vergleich zu den st. gallischen Kliniken Walenstadtberg und Valens hohe Zahl von Pflegetagen für Neuro-Rehabilitationspatienten aus dem Kanton St. Gallen aufweisen soll. Streitfrage hier ist nicht die Aufnahme der Rheinburg-Klinik auf die Spitalliste des Kantons St. Gallen, sondern, welcher Referenztarif bei einer nicht im Sinne von Art. 41 Abs. 2 KVG medizinisch indizierten Behandlung einer Person aus dem Kanton St. Gallen in der genannten Klinik heranzuziehen ist, um die Vergütung durch die obligatorische Krankenpflegeversicherung zu bestimmen. Die Vorinstanz hat richtig ausgeführt, dass es nicht Sache des Krankenversicherers bzw. der angerufenen Gerichte sein kann, Leistungen zuzusprechen, auf die nach den gesetzlichen Vorschriften kein Anspruch besteht, selbst wenn der Kanton St. Gallen für die Durchführung von neurologischen Rehabilitationen auf die Kapazitäten der Rheinburg-Klinik angewiesen sein sollte (vorinstanzliche Erw. 3b in fine). Da der Kanton St. Gallen im Zeitraum der Behandlung in der Rheinburg-Klinik über keine Spitalliste nach Art. 39 Abs. 1 lit. e KVG verfügte, konnte dieses Spital auch nicht als ausserkantonaler Leistungserbringer darauf aufgeführt sein (Art. 41 Abs. 2 lit. b KVG). Die Auffassung der Beschwerdegegnerin, es seien sämtliche ihr durch den Aufenthalt in der betreffenden Klinik entstandenen Kosten zu ersetzen, vermag auch nicht zu stützen, dass, solange der Kanton die in Artikel 39 Absatz 1 Buchstabe e KVG vorgesehene Liste der Spitäler und Pflegeheime noch nicht erstellt hat, gemäss Art. 101 Abs. 2 KVG vorerst früheres Recht des KUVG weiter gilt, und Anstalten oder deren Abteilungen, die nach bisherigem Recht als Heilanstalten galten, als Leistungserbringer nach neuem Recht zugelassen sind. Denn die Leistungspflicht der Versicherer und die Höhe der Vergütung richten sich gemäss Art. 101 Abs. 2 zweiter Satz KVG (nur) bis zu einem vom Bundesrat zu bestimmenden Zeitpunkt nach den bisherigen Verträgen oder Tarifen. Die dafür gesetzte Frist - bis 31. Dezember 1997 gemäss Art. 8 Abs. 1 der Verordnung vom 12. April 1995 über die Inkraftsetzung und Einführung des KVG (SR 832.101) - ist verstrichen. Zudem ist unbestritten, dass für die Kliniken Walenstadtberg und Valens im Kanton St. Gallen und für die Rheinburg-Klinik im Kanton Appenzell Ausserrhoden unter dem neuen Krankenversicherungsrecht Verträge und Tarife vereinbart und genehmigt worden sind. Diese sind anzuwenden, auch wenn noch keine gültige Spitalliste verfügbar ist. Der Umstand, dass ein Spital auf die Spitalliste gesetzt wird, bedeutet einzig, dass es sich dabei um einen zugelassenen Leistungserbringer handelt. Über die Frage des anwendbaren Tarifs ist damit noch nichts gesagt (vgl. BGE 127 V 404 f. Erw. 2b/dd).
5. Da alle drei Rehabilitationskliniken als Leistungserbringer zugelassen und für die Behandlung der Krankheit der Beschwerdegegnerin geeignet sind, konnte sie unter ihnen frei wählen. Weil keine medizinischen Gründe im Sinne von Art. 41 Abs. 2 lit. b KVG für den Aufenthalt in der ausserkantonalen Rheinburg-Klinik bestanden, muss die Beschwerdeführerin die Kosten aber höchstens nach dem Tarif übernehmen, der im Wohnkanton gilt (Art. 41 Abs. 1 dritter Satz KVG). Offen ist damit noch die Frage, welcher Referenztarif zur Anwendung zu gelangen hat. Gemäss der Zusammenstellung der Vereinigung Privatkliniken Schweiz über die bei ihr zusammengeschlossenen Spitäler (abrufbar unter www.privatehospitals.ch) handelt es sich bei allen drei Kliniken um Spitäler mit privater Trägerschaft. Nach der "Liste der nach Art. 39 Abs. 1 oder 101 Abs. 2 KVG zur Krankenversicherung zugelassenen Spitäler" der Schweizerischen Gesundheitsdirektorenkonferenz GDK (Stand 1. Januar 2006; abrufbar unter www.gdk-cds.ch) ist die Klinik Walenstadtberg öffentlich subventioniert, die Institutionen in Valens und Walzenhausen sind es nicht. Alle drei Einrichtungen sind auf Neuro-Rehabilitation spezialisiert.
6. 6.1 Die Vorinstanz hat als Referenztarif die von der Kantonsregierung genehmigten tarifvertraglichen Tagespauschalen der Kliniken Walenstadtberg (Fr. 220.-) und Valens (Fr. 499.-/resp. 541.- ab 1. Januar 2004) in Betracht gezogen. Dass sich die Vorinstanz für den Pauschaltarif der Klinik Valens als Referenztarif entschieden hat, begründet sie im Wesentlichen damit, dass die Beschwerdeführerin zur Kostendeckung nach diesem Tarif verpflichtet gewesen wäre, falls die Beschwerdegegnerin sich in der Klinik hätte behandeln lassen. Da jener die Wahl dieser Klinik gemäss Art. 41 Abs. 4 KVG offen gestanden hätte, habe sie Anspruch auf Kostenersatz in der entsprechenden Höhe.
6.2 Es trifft zwar zu, dass der Beschwerdegegnerin das Wahlrecht unter den zugelassenen stationären Leistungserbringern zustand. Indessen hat sie in einer Weise davon Gebrauch gemacht, bei der das Gesetz zum Vornherein keine volle Kostendeckung aus der obligatorischen Krankenpflegeversicherung vorsieht, denn sie hat es vorgezogen, sich ohne medizinischen Grund im Sinne von Art. 41 Abs. 2 lit. b KVG ausserkantonal behandeln zu lassen. Ihr hier in jedem Fall die Rückvergütung der dabei entstanden Kosten im Umfang des höchsten Tarifs eines zur Behandlung ihrer Krankheit geeigneten innerkantonalen Spitals zu garantieren, ist nicht im Sinne der in Erwägung 3.2 geschilderten Neuordnung des KVG, anders als früher nicht nur das Spital, das dem Wohnort des Versicherten innerhalb des gleichen Kantons am nächsten lag, als Referenzspital zu bezeichnen, sondern neu den Wohnkanton als räumlichen Bereich mit voller Kostenübernahme (vgl. dazu BGE 127 V 145 f. Erw. 4d). Denn dies hätte zur Folge, dass in Kantonen mit hohen Tarifen - allenfalls nur einer einzigen Privatklinik - wohnende Versicherte bei fehlendem medizinischen Grund ihr Wahlrecht ohne Kostenrisiko auf viele oder sämtliche ausserkantonale Spitäler ausdehnen könnten, obwohl dies vom Gesetzgeber nach der Regelung in Art. 41 Abs. 1-3 KVG grundsätzlich nur bei medizinischer Begründetheit gewollt ist.
6.3 Zwar besteht hier nicht - wie bei dem in RKUV 2004 Nr. KV 281 S. 208 f. (Urteil K. vom 12. Dezember 2004, K 34/02) beurteilten Sachverhalt bejaht und in dem in BGE 131 V 133 f. (insbesondere 144 f. Erw. 12.2) erörterten verneint - die Gefahr einer Umgehung der Spitalplanung, da die betreffenden Spitäler ja im Standortkanton eingeplant sind. Aber dem Wohnkanton verbleibt keine Möglichkeit, solchen Entwicklungen Gegensteuer zu geben, da er nur die Befugnis hat, ausserkantonale Kliniken auf seine Spitalliste zu setzen (Art. 41 Abs. 2 lit. b KVG), nicht aber, sie auszugrenzen. Zwar verbliebe ihm theoretisch die Möglichkeit, zur Verhinderung hoher Referenztarife gar keine nicht subventionierten Privatkliniken auf seine Spitalliste aufzunehmen. Dies widerspräche aber dem klar geäusserten gesetzgeberischen Willen, private Trägerschaften seien angemessen in die Spitalplanung einzubeziehen (Art. 39 Abs. 1 lit. d KVG). Nach dem Gesagten entspricht die von der Vorinstanz gefundene Lösung, die versicherte Person habe auf jeden Fall Anspruch auf Vergütung der Kosten im Umfang des höchsten in ihrem Wohnkanton gültigen Tarifs eines zur Behandlung ihrer Krankheit geeigneten Spitals, nicht den Vorstellungen des Gesetzgebers, denn sowohl der Grundsatz "volle Kostendeckung bei medizinisch begründeter ausserkantonaler Hospitalisation" sowie die mit der Pflicht der Kantone zu einer "bedarfsgerechten" Spitalplanung verfolgten Absichten würden zum Teil vereitelt.
7. Demgegenüber macht die Beschwerdeführerin geltend, das Wirtschaftlichkeitsgebot habe im Einzelfall Anwendung zu finden und gemäss Rechtsprechung (BGE 127 V 143) sei es bei medizinisch gleichwertigen, aber unterschiedlich preiswerten innerkantonalen Behandlungsangeboten zu berücksichtigen. Deshalb sei auf den tieferen Tarif der Klinik Walenstadtberg abzustellen.
7.1 Auch diese Lösung ist nicht geeignet. Das Wirtschaftlichkeitsgebot greift in diesem Zusammenhang nicht, da nicht gesagt werden kann, die Behandlung in der Rheinburg-Klinik (oder der Klinik Valens) sei nicht wirtschaftlich: Für beide Kliniken liegen von der Kantonsregierung oder vom Bundesrat bewilligte Tarife vor; diese sind nach Art. 46 Abs. 4 KVG von der Genehmigungsbehörde darauf überprüft worden, ob sie mit dem Gesetz und dem Gebot der Wirtschaftlichkeit und Billigkeit in Einklang stehen. Zudem ist unbestritten, dass die bei der Neuro-Rehabilitation erbrachten Leistungen der Rheinburg-Klinik sich auf ein Mass beschränkten, das im Interesse der Versicherten lag und für den Behandlungszweck erforderlich war (Art. 56 Abs. 1 KVG), und dass die spitalbedürftige Beschwerdegegnerin eine Spitalabteilung wählte, in die sie vom medizinischen Standpunkt aus gehörte. Im Übrigen bezieht sich die von der Beschwerdeführerin zitierte Rechtsprechung BGE 127 V 143 auf die ausserkantonale stationäre Behandlung aus medizinischen Gründen und damit auf eine grundlegend andere Fragestellung als hier.
7.2 Im Weitern ist zu beachten, dass die innerkantonal grosse Tarifdifferenz zwischen den Kliniken Walenstadtberg und Valens dadurch bedingt ist, dass erstere öffentlich subventioniert ist und die im Kanton St. Gallen wohnenden Versicherten sie über ihre Steuern mitfinanzieren. Die von der obligatorischen Krankenpflegeversicherung zu vergütende Pauschale der Privatklinik Walenstadtberg hat darum höchstens 50 Prozent der anrechenbaren Kosten je Patient oder Patientin oder je Versichertengruppe in der allgemeinen Abteilung zu decken. Zudem werden Betriebskostenanteile aus Überkapazität, Investitionskosten sowie Kosten für Lehre und Forschung nicht angerechnet (Art. 49 Abs. 1 Sätze 2 und 4 KVG). Der Tarif der nicht subventionierten Privatklinik Valens hingegen hat die gesamten anrechenbaren Kosten und zusätzlichen Betriebskostenanteile abzudecken, denn auch er hat der gesetzlichen Vorgabe in Art. 43 Abs. 4 KVG zu genügen, betriebswirtschaftlich bemessen und sachgerecht strukturiert zu sein. Wenn nach der von der Beschwerdeführerin vertretenen Auffassung die St. Galler Versicherten ihren nicht medizinisch bedingten ausserkantonalen Spitalaufenthalt ausschliesslich nach der niedrigsten innerkantonalen Referenztaxe vergütet erhalten sollen, wird nicht berücksichtigt, dass sie als Steuerzahlende den (effektiv um mehr als das Doppelte höheren) Tarif bereits mitfinanziert haben. Anderseits würden die gleichen Versicherten - nun als Prämienzahlende - bei der von der Vorinstanz entschiedenen "Maximalvariante" zusätzlich belastet, wenn für die Vergütung ausserkantonaler Spitalaufenthalte immer der höchste innerkantonale Tarif die Referenztaxe abgeben würde. Die obligatorische Krankenpflegeversicherung würde in vielen Fällen sogar stärker beansprucht als bei Vorliegen medizinischer Gründe für die ausserkantonale Behandlung; denn dann hätte der Wohnkanton bei der Behandlung im öffentlichen oder öffentlich subventionierten ausserkantonalen Spital die Differenz zwischen den in Rechnung gestellten Kosten und den Tarifen des betreffenden Spitals für Einwohner und Einwohnerinnen des Kantons zu übernehmen und damit mindestens die Hälfte der Kosten zu tragen (vgl. oben Erw. 3.1).
8. Bei der geschilderten Konstellation gegenläufiger Interessen der Kantone, Spitäler, Versicherer und Versicherten sowie unter den genannten gesetzlichen (Ziel-)Vorgaben kann der Referenztarif nicht tunlichst tief oder hoch festgesetzt werden, sondern es ist ein möglichst zweckmässiger Ausgleich zu schaffen. Zunächst ist die durch die öffentliche Subventionierung der Klinik Walenstadtberg geschaffene "Unvergleichbarkeit der Tarife" der beiden einzigen innerkantonalen Referenzspitäler zu beseitigen. Dazu sind im Pauschaltarif der Klinik Walenstadtberg die in Art. 49 Abs. 1 KVG genannten Kosten aufzurechnen. Dann ist zu ermitteln, in welchem Verhältnis im Jahre 2003 - die Beschwerdegegnerin traf ihre Spitalwahl auf Mitte Dezember 2003 - die in ihrem Wohnkanton gebliebenen St. Galler Rehabilitationspatienten ihr Wahlrecht zwischen den beiden Referenzkliniken ausgeübt haben. Mit dem so berücksichtigten "typischen Wahlverhalten" der St. Galler Versicherten wird einerseits dem Umstand Rechnung getragen, dass anders als früher unter dem KUVG nicht nur das Spital, das dem Wohnort des einzelnen Versicherten innerhalb des gleichen Kantons am nächsten liegt, als Referenzspital zu bezeichnen ist, sondern neu der Wohnkanton als räumlicher Bereich mit voller Kostenübernahme gilt (vgl. oben Erw. 3.2 und 6.2). Anderseits wird berücksichtigt, dass der Gesetzgeber nach der Regelung in Art. 41 Abs. 1-3 KVG nur bei medizinischer Begründetheit das Wahlrecht ohne grundsätzliches Kostenrisiko (vgl. auch BGE 127 V 143) auf viele oder sämtliche ausserkantonale Spitäler ausdehnen wollte. Das "typische Wahlverhalten" bemisst sich nach der Anzahl Pflegetage, welche sämtliche im Kanton St. Gallen tätigen Krankenversicherer für die im betreffenden Kanton wohnhaften Patienten den Kliniken Walenstadtberg und Valens zu vergüten hatten. Der aufgerechnete und angepasste Tarif der Klinik Walenstadtberg des Jahres 2003 und der Tarif der Klinik Valens sind dann bei der Festsetzung des Referenztarifes entsprechend den erhobenen Pflegetagen zu gewichten.
Die Vorinstanz wird die massgeblichen Faktoren für den hier zur Diskussion stehenden Zeitraum erheben und den Referenztarif berechnen, um dann im Sinne der Erwägungen neu zu entscheiden.
Demnach erkennt das Eidg. Versicherungsgericht:
1. In teilweiser Gutheissung der Verwaltungsgerichtsbeschwerde wird der Entscheid des Versicherungsgerichts des Kantons St. Gallen vom 19. Juli 2005 aufgehoben, und es wird die Sache an die Vorinstanz zurückgewiesen, damit sie über die Beschwerde gegen den Einspracheentscheid vom 18. November 2004 im Sinne der Erwägungen neu entscheide.
2. Es werden keine Gerichtskosten erhoben.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Bundesamt für Gesundheit zugestellt.
Luzern, 20. Dezember 2006
Im Namen des Eidgenössischen Versicherungsgerichts
Die Präsidentin der I. Kammer: Der Gerichtsschreiber: