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.