Sachverhalt:
A. R._, geboren 1953, wohnhaft im Kanton Zürich, ist bei der Wincare Versicherungen obligatorisch krankenpflegeversichert. Sie leidet an einer Multisystemerkrankung des zentralen Nervensystems, die unter anderem zu einer Gehstörung führt. Zur Verbesserung des Gangbildes begab sie sich ab 1998 jährlich zur stationären Rehabilitation in die Klinik X._ (Kanton Aargau). Dieses Spital mit privater Trägerschaft ist Bestandteil der Zürcher Spitalliste A (Institutionen mit Zulassung zur Versorgung von Patientinnen und Patienten in der Allgemeinen Abteilung zu Lasten der obligatorischen Krankenpflegeversicherung) mit dem Leistungsauftrag neurologische, orthopädische und rheumatologische Rehabilitation. Die Wincare übernahm für diese Aufenthalte jeweils die Kosten in der Höhe der mit der Klinik X._ vertraglich festgelegten Tagespauschale von zuletzt (Jahr 2004) Fr. 545.-.
Auch vom 28. Oktober bis 24. November 2005 hielt sich R._ wieder zur stationären Rehabilitation in der Klinik X._ auf. Die Wincare übernahm die Kosten nur im Rahmen eines Referenztarifs für eine solche Behandlung in der zürcherischen Klinik Y._ (Tagespauschale von Fr. 123.- und einmalige Fallpauschale von Fr. 1'100.-). Daran hielt sie mit Verfügung vom 6. Juni 2006 und Einspracheentscheid vom 18. Dezember 2006 fest.
B. Die von R._ dagegen erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 23. Mai 2008 gut, hob den Einspracheentscheid auf und verpflichtete die Wincare, für den Rehabilitationsaufenthalt in der Klinik X._ vom 28. Oktober bis 24. November 2005 die Kosten nach dem Standorttarif für ausserkantonale Patientinnen und Patienten zu übernehmen.
C. Die Wincare erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Rechtsbegehren, der kantonale Entscheid sei aufzuheben; sie habe für den streitigen Rehabilitationsaufenthalt nur die Kosten des Referenzspitals Klinik Y._ (Tagespauschale Fr. 123.- und einmalige Fallpauschale von Fr. 1'100) zu übernehmen.
R._ schliesst auf Abweisung der Beschwerde. Das Bundesamt für Gesundheit verzichtet auf eine Vernehmlassung.

Erwägungen:
1. Es steht fest und ist unbestritten, dass die Beschwerdegegnerin die ausserhalb ihres Wohnkantons gelegene, auf der Spitalliste des Kantons Zürich aufgeführte Klinik X._ nicht in einer Notfallsituation aufgesucht hat und dass die streitbetroffene Therapie grundsätzlich auch in einer im Kanton Zürich gelegenen Heilanstalt (Klinik Y._) möglich gewesen wäre.
2. In der vorliegend anwendbaren, bis 31. Dezember 2008 gültig gewesenen Fassung sah <ref-law> vor, dass die Versicherten unter den zugelassenen Leistungserbringern, die für die Behandlung ihrer Krankheit geeignet sind, frei wählen können (Abs. 1 Satz 1) und dass der Versicherer bei stationärer oder teilstationärer Behandlung die Kosten höchstens nach dem Tarif übernehmen muss, der im Wohnkanton der versicherten Person gilt (Abs. 1 Satz 3). In Absatz 2 Satz 1 derselben Bestimmung war geregelt, dass sich die Kostenübernahme, wenn Versicherte aus medizinischen Gründen einen anderen Leistungserbringer beanspruchen, nach dem Tarif richtet, der für diesen Leistungserbringer gilt. Medizinische Gründe lagen (ausser in den hier nicht zur Diskussion stehenden Notfällen) bei stationärer oder teilstationärer Behandlung vor, wenn die erforderlichen Leistungen im Wohnkanton oder in einem auf der Spitalliste des Wohnkantons aufgeführten ausserkantonalen Spital nicht angeboten wurden (Abs. 2 lit. b KVG).
3. 3.1 Das Eidg. Versicherungsgericht hat in <ref-ruling> (auf den sich die Beschwerdeführerin beruft) in einer analogen Situation (Aufenthalt einer im Kanton Basel-Stadt wohnhaften Versicherten in einer im Kanton Basel-Landschaft gelegenen, auf der gemeinsamen Spitalliste Basel-Stadt/Basel-Landschaft aufgeführten Klinik) entschieden, die obligatorische Krankenpflegeversicherung müsse die Kosten nur im Umfang desjenigen Tarifs übernehmen, der im Wohnkanton der Versicherten gelte (bestätigt in RKUV 2003 KV Nr. 254 S. 234, K 77/01 E. 5.4; Urteil K 156/05 vom 30. März 2006 E. 5.2; K 50/03 vom 3. Dezember 2003 E. 6). Zur Begründung führte es aus, dass zwischen der Frage der Zulassung der Leistungserbringer (Art. 35-40 KVG) einerseits und der tarifvertraglichen Rechtslage nach <ref-law> andererseits zu unterscheiden sei. <ref-law> nenne die Voraussetzungen, unter denen ein Patient sich zu Lasten der sozialen Krankenversicherung bei vollem Tarifschutz in einem ausserkantonalen Spital behandeln lassen könne. Wenn ein Kanton ein ausserkantonales Spital auf seine Spitalliste setze, so sei dies zwar zulässig, bedeute aber nur, dass es sich dabei um einen zugelassenen Leistungserbringer handle, welcher KVG-pflichtige Kostenvergütungsansprüche auslöse, sage aber nichts aus über die Frage des anwendbaren Tarifs. Dafür bleibe im Regelfall <ref-law> massgebend, ausser wenn medizinische Gründe im Sinne von <ref-law> vorlägen. Die gegenteilige Auffassung stehe im Widerspruch zu den Materialien.
3.2 Die Vorinstanz weicht bewusst von <ref-ruling> ab. Sie führt unter Hinweis auf die Materialien zu <ref-law> aus, die ausserkantonalen Spitäler auf der Spitalliste seien gleich zu behandeln wie die eigenen kantonalen Spitäler. Damit sollten Anreize gesetzt werden, dass die Kantone im Sinne einer gesamthaften Planung und mittels Aushandelns attraktiver Tarife für die eigenen Kantonseinwohner miteinander zusammenarbeiten. Bei einer solchen Zusammenarbeit werde ein ausserkantonales Spital zu einem innerkantonalen. Der erhöhte Tarif solle nicht schon dann zur Anwendung gelangen, wenn eine bestimmte Behandlung im Wohnkanton nicht angeboten werde, sondern erst dann, wenn es diese Behandlung auch auf der mit ausserkantonalen Spitälern versehenen Spitalliste des Wohnkantons nicht gebe. Der volle Tarifschutz nach <ref-law> werde damit auf die ausserkantonale Behandlung in Listenspitälern des Wohnkantons ausgedehnt. Im Rahmen einer systematischen Auslegung von <ref-law> sei auch zu berücksichtigen, dass der Kanton Zürich im Sinne der vom Gesetz ermöglichten interkantonalen Zusammenarbeit 80 % des gesamten kantonalen Bedarfs an Infrastruktur für stationäre Rehabilitationsaufenthalte mit ausserkantonalen Kliniken abdecke. Es wäre systemwidrig und mit dem Grundsatz der Rechtsgleichheit nicht vereinbar, die stationäre Behandlung in einem Listenspital im Wohnkanton und jene ausserhalb des Wohnkantons unterschiedlich zu behandeln.
3.3 Der Rechtsprechung gemäss <ref-ruling> erwuchs auch in der Lehre Kritik. Dem Bundesgericht wurde vorgeworfen, die Materialien zu <ref-law> falsch interpretiert zu haben (Roggo/Staffelbach, Interkantonale Spitalplanung und Kostentragung - Stellenwert der "geschlossenen Spitalliste" im Falle von "medizinischem Grund im weiteren Sinne", AJP 2006 S. 267 ff., 273 ff.). Sodann wurde postuliert, bei einer Behandlung in einem ausserkantonalen Listenspital müsse gleich wie bei einem innerkantonalen der volle Tarifschutz bestehen, weil sonst die angestrebte interkantonale Zusammenarbeit bei der Grundversorgung behindert werde (Beat Meyer, Schranken und Freiräume von <ref-law>, in: Ausserkantonale Hospitalisation, Thomas Gächter [Hrsg.], 2006, S. 1-16, 8 f.).
3.4 Ob diese Kritik berechtigt ist, braucht vorliegend nicht geprüft zu werden. Denn der zu beurteilende Fall ist - bedingt durch die kantonale Spitalplanung - insofern speziell gelagert, als im Kanton Zürich nur gerade etwas mehr als 20 % des Bedarfs an Infrastruktur für stationäre Rehabilitationsaufenthalte durch innerkantonale Kliniken gedeckt werden kann (vgl. Schreiben der Gesundheitsdirektion vom 30. August 2005) und mithin die Mehrheit der Zürcher Versicherten auf ausserkantonale, auf der Zürcher Spitalliste aufgeführte Rehabilitationskliniken, wie die von der Beschwerdegegnerin seit 1998 jährlich aufgesuchte Klinik X._, angewiesen ist (vgl. auch Bundesamt für Statistik [BFS], Krankenhausstatistik 2005, Tabelle D1, wonach der Kanton Zürich in Rehabilitationskliniken nur gerade über 144 Betten verfügt, was gemessen an der ständigen Wohnbevölkerung von 1'272'590 [vgl. Bundesamt für Statistik, Statistik des jährlichen Bevölkerungsstandes ESPOP 2005] auch im interkantonalen Vergleich einem geringen Versorgungsgrad entspricht). Greift der Kanton Zürich in seiner Spitalplanung für stationäre Rehabilitationsaufenthalte der Wohnbevölkerung zu rund 80 % auf ausserkantonale Kliniken zurück, kommt dies einem fehlenden Angebot innerkantonaler Behandlungsmöglichkeiten derart nahe, dass es sich rechtfertigt, auch diese geplante Auslagerung des Rehabilitationsbedarfs in ausserkantonale Kliniken als medizinischen Grund im Sinne von <ref-law> gelten zu lassen (vgl. betr. Kapazitätsengpässe auch RKUV 2003 KV Nr. 254 S. 234, K 77/01 E. 5.1 und Urteil K 29/93 vom 4. August 1993: vgl. auch Eugster, Krankenversicherung, in: Schweizerisches Bundesverwaltungsrecht [SBVR], Soziale Sicherheit, 2. Aufl. 2007, Rz. 965 S. 724 f.). Nur diese (weite) Interpretation der medizinischen Gründe nach <ref-law> wird dem Grundgedanken des KVG, dass die medizinisch indizierte Versorgung tarifgeschützt im Rahmen der Grundversicherung erfolgen können soll, gerecht.
3.5 Ein Blick auf die am 1. Januar 2009 in Kraft getretene Bestimmung des <ref-law> zeigt zudem, dass der Gesetzgeber im Rahmen der Änderung vom 21. Dezember 2007 noch weiter gegangen ist, indem er nunmehr vorsieht, dass die versicherte Person für die stationäre Behandlung frei wählen kann unter den Spitälern, die auf der Spitalliste ihres Wohnkantons oder jener des Standortkantons aufgeführt sind (Listenspital; Satz 1), und dass der Versicherer und der Wohnkanton bei stationärer Behandlung in einem Listenspital die Vergütung anteilsmässig nach <ref-law> höchstens nach dem Tarif übernehmen, der in einem Listenspital des Wohnkantons für die betreffende Behandlung gilt (Satz 2). Damit ist auch bei einer ausserkantonalen Behandlung in einem Listenspital des Wohnkantons der volle Tarifschutz gewährleistet.
3.6 Sind nach dem Gesagten medizinische Gründe für den Aufenthalt in der Klinik X._ im Falle der Beschwerdegegnerin zu bejahen, hat die Beschwerdeführerin die Kosten nach dem für dieses Spital geltenden Tarif (Standorttarif) zu übernehmen, wie die Vorinstanz im Ergebnis zutreffend erkannt hat.
4. Das Verfahren ist kostenpflichtig (<ref-law>). Als unterliegende Partei hat die Beschwerdeführerin die Gerichtskosten zu tragen (<ref-law>). Überdies hat sie der Beschwerdegegnerin eine Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 27. April 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Keel Baumann