3.1 Die Vorinstanz hat erwogen, grundsätzlich könnten die Krankenversicherer gemäss Art. 25 ATSG (in Verbindung mit Art. 1 Abs. 1 KVG) bzw. nach dem in der Krankenversicherung vor Inkrafttreten des ATSG analog anwendbaren aArt. 47 AHVG (in Kraft bis 31. Dezember 2002; vgl. BGE 126 V 23 E. 4a; zur zeitlichen Anwendbarkeit dieser beiden Bestimmungen: BGE 130 V 318) Leistungen zurückverlangen, soweit die Beschwerdegegnerin mehr Patienten zu Lasten der obligatorischen Krankenpflegeversicherung behandelt habe, als in der Spitalliste Betten zugelassen waren.

3.2 Die obligatorische Krankenpflegeversicherung vergütet nur Leistungen, welche von zugelassenen Leistungserbringern erbracht werden (Art. 35 ff. sowie Art. 41 Abs. 1 KVG; GEBHARD EUGSTER, Krankenversicherung, in: Schweizerisches Bundesverwaltungsrecht [SBVR], Soziale Sicherheit, 2. Aufl., Basel 2007, S. 652 f. Rz. 772). Werden Vergütungen an nicht zugelassene Leistungserbringer ausgerichtet, sind sie unrechtmässig erbracht und deshalb gemäss Art. 25 ATSG in Verbindung mit Art. 1 Abs. 1 KVG zurückzuerstatten. Dies entsprach auch bereits der Rechtsprechung des damaligen Eidg. Versicherungsgerichts vor Inkrafttreten des ATSG in analoger Anwendung von aArt. 47 AHVG (Urteil K 84/92 vom 25. August 1993, publ. in: RKUV 1993 Nr. K 924 S. 172, E. 3 und 4; Urteil K 170/97 vom 23. Juni 1999, E. 5; vgl. auch Urteil K 119/04 vom 6. Oktober 2005, E. 5).

3.3 Dieser Grundsatz gilt auch für Spitäler: Wird ein Spital nicht in die Spitalliste (Art. 39 Abs. 1 lit. e KVG) aufgenommen oder widerspricht es der kantonalen Planung, so hat es keinen Anspruch auf Leistungen der obligatorischen Krankenpflegeversicherung (BGE 132 V 6 E. 2.4.1 S. 11 f.; BGE 125 V 448 E. 3b S. 453 f.; EUGSTER, a.a.O., S. 648 f. Rz. 762 f. und S. 652 f. Rz. 772; ALFRED MAURER, Das neue Krankenversicherungsrecht, Basel 1996, S. 69; THOMAS MATTIG, Grenzen der Spitalplanung aus verfassungsrechtlicher Sicht, Zürich 2003, S. 38; PAUL RICHLI, Die Spitalliste - Ein Planungsinstrument mit staats- und verwaltungsrechtlichen Geburtsgebrechen?, in: Das Recht in Raum und Zeit, Festschrift für Martin Lendi, Zürich 1998, S. 407 ff., 411; kritisch dazu JEAN-LOUIS DUC, Révisions de la LAMal, in: Bettina Kahil-Wolff [Hrsg.], Les assurances sociales en révision, Lausanne 2002, S. 157 ff., 179 ff., mit der Argumentation, die Versicherten würden mit dieser Konsequenz ihres in Art. 41 KVG statuierten Rechts auf freie Wahl der Leistungserbringer beraubt, wobei er aber übersieht, dass Art. 41 KVG dieses Recht ausdrücklich nur in Bezug auf die zugelassenen Leistungserbringer festhält). Werden trotzdem solche Leistungen ausbezahlt, erfolgen diese unrechtmässig und sind nach Art. 25 ATSG zurückzuerstatten.

3.4 Dem kann auch nicht entgegengehalten werden, dass die Patienten, welche im planungswidrigen Spital behandelt worden sind, eine Behandlung erhalten haben, die sie sonst in einem anderen Spital (ebenfalls zu Lasten der Krankenversicherung) erhalten hätten. Denn die Spitalplanung bezweckt unter anderem eine Eindämmung der Kosten, indem der Gesetzgeber davon ausgeht, dass ein Überangebot an Betten tendenziell zu einer vermehrten Inanspruchnahme von Leistungen führt (BBl 1992 I 166 f.; BGE 132 V 6 E. 2.4.1 S. 12; BGE 125 V 448 E. 3b S. 453 f.; E. II.3.1 des in RKUV 1997 Nr. KV 2 S. 1 publizierten Entscheids des Bundesrates vom 2. Dezember 1996; EUGSTER, a.a.O., S. 642 f., S. 706 Rz. 914; MAURER, a.a.O., S. 69; RICHLI, a.a.O., S. 411). Der Grundsatz, dass nur die in der Spitalliste enthaltenen Spitäler zugelassene Leistungserbringer sein können, dient damit auch dem Wirtschaftlichkeitsziel (Art. 32 KVG), dessen Verletzung durch Art. 56 KVG sanktioniert wird. Wurde eine Vergütung an ein nicht auf der Liste aufgeführtes Spital bezahlt, erfolgte diese zu Unrecht; die erbrachte Leistung kann aufgrund von Art. 56 Abs. 2 KVG, dessen Wortlaut nicht etwa bloss von Ärzten, sondern generell von Leistungserbringern (und damit auch von Spitälern) spricht, zurückverlangt werden.

3.5 Im angefochtenen Entscheid wird daher mit Recht von einer grundsätzlich bestehenden Rückerstattungspflicht ausgegangen.

4. Das kantonale Schiedsgericht hat indessen erwogen, die Beschwerdeführer hätten spätestens mit der Zustellung der Eingabe der Beschwerdegegnerin vom 27. Januar 2003 (Ende Januar oder Anfang Februar 2003) gewusst, dass diese mehr Spitalbetten betrieb als gemäss Spitalliste zugelassen. Die erst am 31. März 2004 erhobene Klage sei daher gemäss Art. 25 Abs. 2 ATSG bzw. aArt. 47 Abs. 2 AHVG verwirkt.

4.1 Nach Art. 25 Abs. 2 Satz 1 ATSG erlischt der Rückforderungsanspruch mit dem Ablauf eines Jahres, nachdem die Versicherungseinrichtung davon Kenntnis erhalten hat, spätestens aber mit dem Ablauf von fünf Jahren nach Entrichtung der einzelnen Leistung. Dasselbe galt nach aArt. 47 Abs. 2 Satz 1 AHVG, in welcher Bestimmung zwar von einer Verjährungsfrist die Rede war, welche aber vom Eidg. Versicherungsgericht in ständiger Praxis als Verwirkungsfrist betrachtet wurde (BGE 119 V 431 E. 3a S. 433). Die gleiche Verwirkungsfrist findet auch Anwendung, soweit der Rückforderungsanspruch statt auf Art. 25 ATSG auf Art. 56 Abs. 2 KVG gestützt wird (vgl. zum Verhältnis zwischen dieser Bestimmung und Art. 25 ATSG bzw. aArt. 47 AHVG: Urteil des Eidg. Versicherungsgerichts K 25/02 vom 23. September 2002, publ. in: RKUV 2002 Nr. KV 230 S. 468, E. 2.2), weil rechtsprechungsgemäss auch auf die dort geregelte Rückforderung die Verwirkungsfrist von aArt. 47 Abs. 2 AHVG (bzw. neu Art. 25 Abs. 2 ATSG) analog angewendet wird (Urteil des Eidg. Versicherungsgerichts K 9/00 vom 24. April 2003, publ. in: RKUV 2003 Nr. KV 250 S. 216, E. 2.1).

4.2 Die Beschwerdeführer machen in ihrer Replik geltend, es sei nicht die Frist von Art. 25 Abs. 2 ATSG massgebend, sondern eine zehnjährige Frist, da der Betrieb von zu vielen Betten eine Verletzung des Tarifvertrags (Art. 49 KVG) darstelle und somit vertragsrechtliche Verjährungsfristen anwendbar seien. Dieser Betrachtung kann nicht gefolgt werden: Das (damalige) Eidg. Versicherungsgericht hat bereits entschieden, dass Rückforderungen zu Unrecht erbrachter Leistungen auch dann nach aArt. 47 AHVG zu beurteilen sind und der dort enthaltenen Verwirkungsregelung unterstehen, wenn es um Rückforderungen aufgrund eines Tarifvertrags geht (Urteil K 84/92 vom 25. August 1993, publ. in: RKUV 1993 Nr. K 924 S. 172, E. 3b). Dies muss auch in Bezug auf die heute in Kraft stehende Bestimmung von Art. 25 ATSG gelten. Die Beschwerdeführer setzen sich mit dieser Rechtsprechung nicht auseinander. Es besteht kein Anlass, sie zu überprüfen, zumal die Beschwerdeführer ihren Rückforderungsanspruch daraus herleiten, dass die Beschwerdegegnerin zu viele Betten betrieben habe, die Anzahl der zugelassenen Betten jedoch nicht im Tarifvertrag, sondern in der vom Kanton erlassenen Spitalliste geregelt ist, so dass ohnehin keine Vertragsverletzung zur Diskussion steht (abgesehen davon, dass ab Juli 2000 ein vertragsloser Zustand bestand).

4.3 Die Beschwerdeführer stellen sich in ihrer Replik sodann auf den Standpunkt, bereits mit dem Schreiben vom 18. Juli 2003 sei die Frist gewahrt worden.

4.3.1 Im Privatrecht kann die Verjährung nur durch die in Art. 135 OR genannten Handlungen unterbrochen werden, wobei der dort enthaltene Begriff der Klageanhebung analog für die Wahrung einer Verwirkungsfrist gilt (BGE 110 II 387 E. 2b S. 389 f.). Im öffentlichen Recht genügen demgegenüber für die Unterbrechung der Verjährung bzw. Wahrung einer Verwirkungsfrist neben den in Art. 135 OR genannten Handlungen alle Akte, namentlich einfache schriftliche Erklärungen, mit denen die Forderung gegenüber dem Schuldner in geeigneter Weise geltend gemacht wird (BGE 87 I 411 E. 2 S. 413 ff.; BGE 85 I 180 E. 3 S. 183 f.; Urteile des Bundesgerichts 1A.15/ 1997 vom 25. August 1997, E. 3 [ZBl 99/1998 S. 489]; 1A.315/1995 vom 10. September 1996, E. 3b [ZBl 98/1997 S. 524]; 2C.3/2005 vom 10. Januar 2007, E. 4.2, 5.4 und 5.7; 2A.553/2002 vom 22. August 2003, E. 4.7 und 4.8; Urteil des Eidg. Versicherungsgerichts B 55/05 vom 16. Oktober 2006, publ. in: SVR 2007 BVG Nr. 18 S. 61, E. 4.2.3; HÄFELIN/MÜLLER/UHLMANN, Allgemeines Verwaltungsrecht, 5. Aufl., Zürich 2006, S. 165 N. 777; ATTILIO GADOLA, Verjährung und Verwirkung im öffentlichen Recht, in: AJP 1995 S. 47 ff., 54; ANDRÉ GRISEL, Traité de droit administratif, Bd. II, Neuenburg 1984, S. 666 f.; ANDREA BRACONI, Prescription et péremption dans l'assurance sociale, in: Droit privé et assurances sociales, Freiburg 1990, S. 215 ff., 232; PIERRE MOOR, Droit administratif, Bd. II, 2. Aufl., Bern 2002, S. 86 f.), ausser wenn das anwendbare Gesetz etwas anderes (Klage usw.) vorsieht (vgl. Urteil des Bundesgerichts 1A.127/1999 vom 22. Dezember 1999, E. 5b und c). Das gilt grundsätzlich auch für die Unterbrechung von Verjährungsfristen bzw. die Wahrung von Verwirkungsfristen im Sozialversicherungsrecht, insbesondere für die Geltendmachung von Leistungen, wo bereits die - auch formlose bzw. fehlerhafte - Anmeldung im Sinne von Art. 29 ATSG zur Fristwahrung ausreicht (BGE 111 V 261 E. 3b S. 264 f.; BGE 103 V 69 E. 1a S. 70; ANDRÉ PIERRE HOLZER, Verjährung und Verwirkung der Leistungsansprüche im Sozialversicherungsrecht, Diss. Freiburg 2005, S. 73; THOMAS LOCHER, Grundriss des Sozialversicherungsrechts, 3. Aufl., Bern 2003, S. 277; UELI KIESER, ATSG-Kommentar, Zürich 2003, N. 13 f. zu Art. 24, N. 27 zu Art. 29 ATSG). Im Beitragsrecht wird freilich zur Fristwahrung eine Verfügung verlangt (BGE 119 V 431 E. 3c S. 434). Dasselbe gilt im Bereich der Arbeitgeberhaftpflicht nach Art. 52 AHVG (BGE 119 V 89 E. 4c S. 96), wo sich dieses Erfordernis ausdrücklich aus aArt. 82 AHVV (in Kraft bis 31. Dezember 2002) ergab. In der Invalidenversicherung hat allerdings das (damalige) Eidg. Versicherungsgericht erkannt, dass unter der Herrschaft des Vorbescheidverfahrens bereits der Vorbescheid die Frist wahrt (BGE 119 V 431 E. 3c S. 434). Im Bereich der beruflichen Vorsorge kann demgegenüber die Frist nur mit einer der in Art. 135 OR genannten Handlungen gewahrt werden; dies wird damit begründet, dass erstens die Rückforderung sich dort nach Art. 62 ff. OR richtet, so dass das Privatrecht anwendbar ist, zweitens die Vorsorgeeinrichtungen keine Verfügungen erlassen können, sondern den Klageweg einzuschlagen haben, und drittens das BVG in aArt. 41 Abs. 1 BVG (in der bis 31. Dezember 2004 in Kraft gestandenen Fassung, welche Bestimmung mit Wirkung ab 1. Januar 2005 zu Art. 41 Abs. 2 BVG wurde) ausdrücklich auf Art. 129-142 OR verweist (Urteil des Eidg. Versicherungsgerichts B 55/05 vom 16. Oktober 2006, publ. in: SVR 2007 BVG Nr. 18 S. 61, E. 4.2.3).

4.3.2 In der Krankenversicherung wird nach bisheriger Rechtsprechung die Verwirkungsfrist für die Rückerstattung einer vom Versicherten zu Unrecht erhaltenen Leistung durch ein formloses Schreiben der rückerstattungsberechtigten Kasse gewahrt; dies wird damit begründet, dass die Krankenversicherer nicht verpflichtet sind, die Leistungen in jedem Fall mittels Verfügung festzulegen (Art. 80 KVG; Urteile des Eidg. Versicherungsgerichts K 4/97 vom 6. Februar 1998, publ. in: RKUV 1998 Nr. K 990 S. 251, E. 2; K 22/89 vom 18. Januar 1990, publ. in: RKUV 1990 Nr. K 835 S. 80, E. 2b). In der Lehre wird allerdings die Auffassung vertreten, dass bei der Rückerstattung gemäss Art. 25 ATSG eine formlose Rückforderung nicht mehr genüge (EUGSTER, a.a.O., S. 616 Rz. 655; KIESER, a.a.O., N. 30 zu Art. 25 ATSG). Dies lässt sich im Verhältnis zwischen Versicherer und versicherter Person allenfalls damit begründen, dass gemäss Art. 3 Abs. 1 ATSV die Rückforderung verfügt werden muss.

4.3.3 Gegenüber den Leistungserbringern kann indessen der Krankenversicherer - anders als die Versicherungsträger in anderen Bereichen der Sozialversicherung - die Rückerstattung zu viel erbrachter Leistungen nicht durch Verfügung, sondern nur durch Klage beim Schiedsgericht geltend machen (Art. 89 KVG; Urteil des Eidg. Versicherungsgerichts K 119/04 vom 6. Oktober 2005, E. 2.2 und 4.1). Auch fehlt - anders als in der beruflichen Vorsorge - ein Verweis auf privatrechtliche Bestimmungen. Die Überlegungen, welche dazu geführt haben, in einzelnen Bereichen der Sozialversicherung in Abweichung vom allgemeinen Verwaltungsrecht eine formlose Rückforderung nicht als fristwahrend gelten zu lassen, sind insoweit nicht massgebend.

4.3.4 Im Bereich der Rückerstattung von Leistungen der Krankenversicherung wegen Überarztung gemäss Art. 56 KVG bzw. Art. 23 KUVG hat das damalige Eidg. Versicherungsgericht in BGE 103 V 145 E. 4 S. 154 erkannt, dass die "Verjährungsfrist" rechtsgültig unterbrochen wird mit dem an die Paritätische Vertrauenskommission gerichteten Gesuch, die Rechnung eines Arztes zu überprüfen und zu kürzen. In der späteren Rechtsprechung wurde jeweils unter Berufung auf diesen Entscheid ausgeführt, zur Fristwahrung müsse das Rückforderungsbegehren bei einer vertraglichen Schlichtungsinstanz oder der gesetzlichen Vermittlungsbehörde oder direkt beim Schiedsgericht eingereicht werden (Urteil des Eidg. Versicherungsgerichts K 9/00 vom 24. April 2003, publ. in: RKUV 2003 Nr. KV 250 S. 216, E. 2.2.1; Urteile K 50/00 vom 30. Juli 2001, E. 3a, und K 39/95 vom 11. Juli 1996, E. 5g; K 73/80 vom 4. Februar 1982, auszugsweise publ. in: RSKV 1982 Nr. 505 S. 201, E. 4b). Im nicht publizierten Urteil K 167/04 vom 18. März 2005, E. 4.2.2, hat das damalige Eidg. Versicherungsgericht erkannt, eine formlose Rückerstattungsforderung sei nicht fristwahrend.

4.3.5 Die Frage nach der fristwahrenden Wirkung anderer Handlungsweisen ist entgegen dem zuletzt genannten Entscheid dort zu bejahen, wo - wie vorliegend - kein obligatorisches Schiedsverfahren besteht. Denn dies entspricht einerseits dem im öffentlichen Recht Üblichen (vgl. vorne E. 4.3.1) und ergibt sich andererseits aus folgender Überlegung: Die Gesetzgebung geht offensichtlich davon aus, dass es dem Gläubiger möglich sein soll, die Frist durch Handlungen zu wahren, die kein grosses Kostenrisiko enthalten. So kann nach Privatrecht die Frist nicht nur durch Klage, sondern auch bereits durch Schuldbetreibung oder Ladung zu einem Sühneversuch gewahrt werden (Art. 135 Ziff. 2 OR). Soweit der Rückerstattungsberechtigte eine Verfügung erlassen kann, ist auch dies für ihn ohne erhebliches Kostenrisiko. Dasselbe gilt im Bereich der Krankenversicherung, soweit eine fristwahrende Anrufung einer obligatorischen Schlichtungsinstanz möglich ist. Wenn hingegen die Frist nur durch Klage gewahrt werden könnte, wäre der Rückerstattungsberechtigte gehalten, bereits zur Fristwahrung ein Verfahren einzuleiten, welches regelmässig ein erhebliches Kostenrisiko mit sich bringt. Das erscheint im Lichte der in den einschlägigen gesetzlichen Regelungen enthaltenen Wertungen als unzumutbar. Zudem wäre die im Interesse des Rechtsfriedens und der Prozessökonomie anzustrebende und zu fördernde gütliche Regelung erheblich erschwert, wenn zwingend innert der relativ kurzen einjährigen Frist eine Klage eingereicht werden müsste; dabei ist zu berücksichtigen, dass angesichts des Verwirkungscharakters der Frist auch keine Verjährungsverzichtsvereinbarung möglich ist, wie sie sonst im Hinblick auf aussergerichtliche Vergleichsverhandlungen üblich ist. Aus diesen Gründen ist in denjenigen Fällen, in denen kein obligatorisches Schlichtungsverfahren besteht und demzufolge direkt Klage beim Gericht zu erheben ist, bereits ein vorangehender Akt, mit welchem der Gläubiger seine Forderung gegenüber dem Schuldner in geeigneter Form geltend macht, als fristwahrend zu betrachten.

4.4 Mit Schreiben vom 18. Juli 2003 haben die Beschwerdeführer von der Beschwerdegegnerin eine Rückforderung im Betrag von Fr. 11'437'541.- verlangt mit der Begründung, die Beschwerdegegnerin habe gemäss ihren eigenen Angaben 66 Betten betrieben; die Krankenversicherer hätten daher für Spitalbehandlungen Leistungen ausgerichtet, für welche teilweise die gesetzlichen Voraussetzungen fehlten. Die Beschwerdeführer haben damit ihre Forderung unmissverständlich geltend gemacht. Bei dieser Sachlage ist die einjährige Verwirkungsfrist mithin gewahrt, sofern sie nicht vor dem 19. Juli 2002 zu laufen begonnen hat.

(...)

9. Insgesamt ergibt sich, dass die Rückforderung für die ab 19. Juli 1998 erbrachten Leistungen nicht verwirkt ist. Der angefochtene Entscheid ist aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen, damit sie materiell über den Rückforderungsanspruch entscheidet.