Sachverhalt:
A. Am 14. Dezember 1990 beschloss die Gemeindeversammlung von Saanen die "Überbauungsordnung Nr. 29 Hotel Alpina, Gstaad", welche die Sanierung des 1907 erstellten Hotels Alpina, seine Erweiterung durch Anbauten und das Erstellen von 45 Résidence-Wohnungen vorsah. Die Überbauungsordnung wurde durch Beschluss des Regierungsrats des Kantons Bern vom 29. April 1992 teilweise abgeändert und genehmigt.
B. Am 11. April 1995 wurde das Hotel Alpina gesprengt, gestützt auf eine Abbruchbewilligung der Baukommission Saanen vom 3. März 1995. Im darauf folgenden Beschwerdeverfahren hob das Verwaltungsgericht des Kantons Bern am 18. März 1996 die Abbruchbewilligung auf. Es stellte fest, die Bau-, Verkehrs- und Energiedirektion des Kantons Bern habe der Beschwerde gegen die Abbruchverfügung verfrüht die aufschiebende Wirkung entzogen. In seinen Erwägungen führte das Verwaltungsgericht u.a. aus, mit dem Abbruch des Hotels seien die planerischen Vorgaben für das interessierende Gebiet obsolet geworden; es müsse daher geprüft werden, ob der Überbauungsordnung von Amtes wegen die Genehmigung zu entziehen sei.
C. Am 15. Mai 1998 stimmte die Gemeindeversammlung von Saanen der "Überbauungsordnung Nr. 56 Hotel Alpina Gstaad" zu, welche die bisherige Überbauungsordnung Nr. 29 ersetzen soll.
Am 9. August 1999 genehmigte das kantonale Amt für Gemeinden und Raumordnung (AGR) in einem Gesamtentscheid die Überbauungsordnung samt Bauvorhaben für ein Hotel mit ca. 160 Betten, eine Hotel-Résidence mit 14 Luxuseigentumswohnungen, drei vorgelagerte Chaletbauten mit insgesamt 14 Luxusappartements, unterirdische Infrastrukturanlagen inkl. Abstellplätze und die Erschliessung der Anlage von Süden über die Palace- und die Alpinastrasse sowie von Norden ab der Neuretstrasse.
Mit Entscheid vom 29. August 2000 hiess die Justiz-, Gemeinde- und Kirchendirektion des Kantons Bern (JGK) die Beschwerden u.a. der F._ SA insoweit gut, als sie die Planung der nördlichen Erschliessung ab der Neuretstrasse nicht genehmigte und die entsprechende Baubewilligung und Rodungsbewilligung aufhob. Im Übrigen wies sie die Beschwerden ab, soweit sie darauf eintrat.
D. Gegen den Entscheid der JGK erhoben die F._ SA, der Berner Heimatschutz und die Helvetia Nostra einerseits und die Einwohnergemeinde Saanen und die E._ AG andererseits Beschwerde ans Verwaltungsgericht. Dieses hiess die Beschwerden der F._ SA, der Helvetia Nostra und des Berner Heimatschutzes am 21. Januar 2002 insoweit gut, als das Hotelprojekt den Grenzabstand zur Parzelle Nr. 100 sowie auf der westlichen Seite die Waldabstandslinie für oberirdische Bauten von 15 m nicht einhielt. Überdies erachtete das Verwaltungsgericht eine Neubeurteilung der Lärmsituation an der Alpina- und der Palacestrasse für notwendig. Es hob deshalb den angefochtenen Entscheid sowie den Gesamtentscheid des AGR auf und wies die Sache zur Überarbeitung im Sinne der Erwägungen an die Gemeinde zurück. Die Beschwerden der Einwohnergemeinde Saanen und der E._ AG gegen die Nichtgenehmigung der nördlichen Erschliessung wies es ab.
E. Am 15. Januar 2003 wies das Bundesgericht eine gegen den Entscheid des Verwaltungsgerichts erhobene Verwaltungsgerichtsbeschwerde der F._ SA ab, soweit darauf einzutreten war (Urteil 1A.42/2002).
F. Am 12. Dezember 2003 stimmte die Gemeindeversammlung von Saanen der Änderung und Neufassung der "Überbauungsordnung Nr. 56 Hotel Alpina Gstaad" zu. Am 2. Juni 2004 genehmigte das AGR in einem neuen Gesamtentscheid die Überbauungsordnung und erteilte die nachgesuchte Baubewilligung für ein Hotel mit 124 Betten, diversen Restaurants und einer Bar, eine Hotel-Résidence mit 13 Luxuseigentumswohnungen, drei vorgelagerte Chaletbauten mit insgesamt 10 Luxusappartements, unterirdische Infrastrukturanlagen und Einstellhallen sowie die Erschliessung der Anlage von Süden über die Palacestrasse und die Alpinastrasse.
G. Hiergegen erhoben u.a. die A._ AG, B._, C._ und D._ Beschwerde bei der JGK. Im Auftrag der JGK erstellte die Planteam GHS AG am 15. März 2005 ein Gutachten zu den Verkehrs- und Lärmprognosen sowie zur Verkehrssicherheit im Bereich der Erschliessung der geplanten Überbauung. Mit Entscheid vom 31. Oktober 2005 wies die JGK die Beschwerden mit Ausnahme eines Nebenpunkts (Rechtsverwahrung und Lastenausgleich) ab, soweit sie auf diese eintrat.
H. Gegen den Entscheid der JGK gelangten sowohl die A._ AG und B._ als auch C._ und D._ mit Beschwerde an das Verwaltungsgericht. Dieses hiess die Beschwerden am 22. Mai 2007 insoweit gut, als es den Entscheid der JGK mit Bestimmungen über die Geschwindigkeitsbegrenzung (30 km/h) und die Bauarbeiten auf der Alpinastrasse ergänzte. Im Übrigen wies es die Beschwerden ab, soweit darauf einzutreten war.
I. Gegen den verwaltungsgerichtlichen Entscheid haben die A._ AG und B._ (1C_176/2007; im Folgenden: Beschwerdeführer 1 und 2) sowie C._ und D._ (1C_177/2007; im Folgenden: Beschwerdeführer 3 und 4) am 22. und 25. Juni 2007 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht erhoben. Sie beantragen die Aufhebung des angefochtenen Entscheids, der Überbauungsordnung Nr. 56 und der Baubewilligung bzw. die Nichtgenehmigung der Überbauungsordnung; eventualiter sei die Sache zur Neubeurteilung an das Verwaltungsgericht bzw. an die kantonalen Bewilligungsbehörden zurückzuweisen.
J. Die E._ AG und die Einwohnergemeinde Saanen beantragen, die Beschwerden seien abzuweisen, soweit darauf eingetreten werden könne, und das Urteil des Verwaltungsgerichts vom 22. Mai 2007 sei zu bestätigen. Das Verwaltungsgericht und die JGK schliessen auf Abweisung der Beschwerden.
Das Bundesamt für Umwelt (BAFU) hält in seiner Vernehmlassung fest, dass der angefochtene Entscheid Bundesumweltrecht nicht verletze. Das Bundesamt für Raumentwicklung (ARE) hat auf eine Stellungnahme verzichtet.
K. In ihren Repliken und ergänzenden Stellungnahmen halten die Beschwerdeführer an ihren Rechtsbegehren fest.
Die E._ AG beantragt mit Eingabe vom 2. Oktober 2007, die Repliken seien aus dem Recht zu weisen.
L. Mit Verfügung vom 24. Juli 2007 wurde den Beschwerden aufschiebende Wirkung beigelegt.

Erwägungen:
1. Da beide Beschwerden denselben Gegenstand betreffen und ähnliche Rügen enthalten, rechtfertigt es sich, die Beschwerdeverfahren zu vereinigen.
2. Weil der angefochtene Entscheid nach dem Datum des Inkrafttretens des Bundesgesetzes über das Bundesgericht (BGG, SR 173.110), dem 1. Januar 2007 (AS 2006, 1242), ergangen ist, untersteht die Beschwerde dem neuen Recht (<ref-law>).
2.1 Gestützt auf <ref-law> beurteilt das Bundesgericht Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung.
2.2 Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten hat, durch den angefochtenen Entscheid besonders berührt ist und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung besitzt (<ref-law>). Verlangt ist somit neben der formellen Beschwer (lit. a), dass der Beschwerdeführer über eine spezifische Beziehungsnähe zur Streitsache verfügt (lit. b) und einen praktischen Nutzen aus der Aufhebung oder Änderung des angefochtenen Entscheids zieht (lit. c). Die Nähe der Beziehung zum Streitgegenstand muss bei Bauprojekten insbesondere in räumlicher Hinsicht gegeben sein. Ein schutzwürdiges Interesse liegt vor, wenn die tatsächliche oder rechtliche Situation des Beschwerdeführers durch den Ausgang des Verfahrens beeinflusst werden kann (<ref-ruling> E. 1.3.1 S. 252).
2.2.1 Alle Beschwerdeführer sind Eigentümer von Chalets bzw. Grundstücken an der Alpina- und Palacestrasse in Gstaad. Sie befürchten übermässige Lärmimmissionen aufgrund des Verkehrsaufkommens der Alpina-Überbauung, die über die Palace- und die Alpinastrasse erschlossen werden soll. Die Beschwerdeführer haben daher eine besonders enge räumliche Beziehung zur streitigen Überbauung und ein schutzwürdiges Interesse an der Aufhebung bzw. Abänderung der angefochtenen Überbauungsordnung und der Baubewilligung.
2.2.2 Die Beschwerdeführer waren am vorinstanzlichen Verfahren beteiligt, das zum angefochtenen Entscheid des Verwaltungsgerichts vom 22. Mai 2007 führte; insoweit sind sie auch formell beschwert.
Fraglich und zwischen den Parteien streitig ist dagegen, ob die Beschwerdeführer auch berechtigt sind, Rechtsfragen vor Bundesgericht aufzuwerfen, die schon das ursprüngliche Überbauungsprojekt betrafen und über die das Verwaltungsgericht in seinem Entscheid vom 21. Januar 2002 entschieden hat. Am Beschwerdeverfahren gegen die erste Fassung der ÜO Nr. 56 hatten sich die Beschwerdeführer nicht beteiligt.
Grundsätzlich können zusammen mit dem kantonal letztinstanzlichen Endentscheid (hier: der Verwaltungsgerichtsentscheid vom 22. Mai 2007) auch Vor- und Zwischenentscheide mitangefochten werden, gegen welche nicht selbständig Beschwerde geführt werden konnte (<ref-law>). Dazu gehören auch frühere Rückweisungsentscheide der kantonalen Instanz (<ref-ruling> E. 4.2 S. 481 f.).
Das Urteil des Verwaltungsgerichts vom 21. Januar 2002, mit dem die Sache zur Überarbeitung im Sinne der Erwägungen an die Gemeinde zurückgewiesen wurde, konnte nach der bundesgerichtlichen Praxis zum OG mit Verwaltungsgerichtsbeschwerde wegen Verletzung von Bundesverwaltungsrecht selbständig angefochten werden, soweit es bereits einen Grundsatzentscheid in der Sache enthielt; dagegen konnten planungsrechtliche Rügen erst mit staatsrechtlicher Beschwerde gegen den Endentscheid geltend gemacht werden (vgl. Entscheid 1A.42/2002 vom 15. Januar 2003 E. 5). Diese Rügen können daher, nach Inkrafttreten des BGG, grundsätzlich noch mit Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben werden, zusammen mit der Beschwerde gegen den Endentscheid.
Voraussetzung ist allerdings, dass die Beschwerdeführer auch hinsichtlich der vorangegangenen Zwischenentscheide formell beschwert sind. Dies ergibt sich seit dem 1. Januar 2007 aus <ref-law>, galt aber schon nach der bundesgerichtlichen Rechtsprechung zum OG (vgl. zur Verwaltungsgerichtsbeschwerde <ref-ruling> E. 1a S. 359 mit Hinweisen; Fritz Gygi, Bundesverwaltungsrechtspflege, 2. Aufl., Bern 1983, S. 155; zur staatsrechtlichen Beschwerde <ref-ruling> E. 1b S. 79; unveröffentlichter Entscheid 1A.141/1995 vom 28. Dezember 1995 E. 3). Das Bundesgericht verzichtete auf dieses Erfordernis, wenn die Beschwerdeführer, ohne ihr Verschulden, am vorinstanzlichen Verfahren nicht hatten teilnehmen können. Dies ist auch dann der Fall, wenn das Rechtsschutzbedürfnis erst nachträglich entstanden ist, d.h. die Beschwerdeführer erstmals durch den angefochtenen Entscheid beschwert wurden (Isabelle Häner, Die Beteiligten im Verwaltungsverfahren und Verwaltungsprozess, Zürich 2000, S. 179 f. Rz 331 und 333).
Die Beschwerdeführer hatten z.T. Einsprache gegen die erste Fassung der ÜO erhoben, sich aber am Beschwerdeverfahren nicht beteiligt. Unstreitig wären sie schon damals als Nachbarn zur Beschwerde legitimiert gewesen. Dies gilt in besonderem Masse für die Beschwerdeführer 3 und 4, von deren Land ein Streifen für die (schon in der ersten Fassung der ÜO Nr. 56 vorgesehene) Verbreiterung der Alpinastrasse beansprucht wird. Von Anfang an geplant war auch die Erschliessung der Alpina-Überbauung über die Alpina- und die Palacestrasse. Die Norderschliessung über die Neuretstrasse, die später von der JGK nicht genehmigt wurde, sollte vor allem dem Baustellen- sowie dem Zuliefer- und Personalverkehr dienen. Insofern hätten die Beschwerdeführer Anlass gehabt, schon die erste Fassung der ÜO anzufechten, wenn sie mit der geplanten Überbauungsordnung und dem Bauprojekt in grundsätzlicher Weise nicht einverstanden waren. Wenn sie darauf verzichteten und sich erst am kantonalen Beschwerdeverfahren gegen die geänderte Fassung der ÜO Nr. 56 beteiligten, so können sie vor Bundesgericht auch nur den in diesem Verfahrensteil ergangenen Entscheid des Verwaltungsgerichts anfechten. Mangels formeller Beschwer sind sie dagegen nicht legitimiert, den ersten verwaltungsgerichtlichen Entscheid vom 21. Januar 2002 mitanzufechten.
Eine andere Frage ist, ob das Verwaltungsgericht im Entscheid vom 22. Mai 2007 bestimmte Rechtsfragen, über die es bereits im Entscheid vom 21. Januar 2002 entschieden hatte, nochmals hätte prüfen müssen. Dies ist keine Frage des Eintretens, sondern der materiellen Beurteilung des angefochtenen Entscheids (vgl. dazu unten, E. 3).
2.3 Nach dem Gesagten ist auf die Beschwerde einzutreten, soweit sie sich gegen den Endentscheid des Verwaltungsgerichts vom 22. Mai 2007 richtet.
2.4 Die Beschwerdegegnerin verlangt, die Repliken der Beschwerdeführer seien aus dem Recht zu weisen.
Dieser Antrag ist unbegründet, weil die Beschwerdeführer gemäss Art. 29 Abs. 1 und 2 BV das Recht haben, sich zu den Beschwerdeantworten zu äussern, unabhängig davon, ob diese neue Tatsachen oder Argumente enthalten (<ref-ruling> E. 2.1 S. 99, 100 E. 4 S. 101 ff.). Unberechtigt ist sodann der Vorwurf, das Gericht sei seiner Pflicht zur Zustellung der Vernehmlassungen nicht nachgekommen: Dies geschah mit Verfügung vom 2. November 2007. Praxisgemäss werden sämtliche Vernehmlassungen zusammen übermittelt, weshalb mit der Zustellung bis zum Eingang des Vernehmlassungsverzichts des ARE abgewartet wurde.
3. Die Beschwerdeführer rügen eine Verletzung von Art. 29 Abs. 1 und 2 sowie <ref-law>, weil das Verwaltungsgericht auf alle Rügen nicht mehr eingetreten ist, über die es schon mit Urteil vom 21. Januar 2002 abschliessend entschieden hatte.
3.1 Die Beschwerdeführer sind der Auffassung, das Verwaltungsgericht hätte sich nicht auf die Fragen des Verfahrens-, des Lärm- sowie des Planungs- und Baurechts beschränken dürfen, die aufgrund der Änderungen der ÜO Nr. 56 und der entsprechenden Baubewilligung neu zu beurteilen gewesen seien; vielmehr hätte es die Zugehörigkeit des Alpina-Areals zur Bauzone, das öffentliche Interesse und den Bedarf an der Errichtung eines neuen Luxushotels und neuer Zweitwohnungsbauten sowie Fragen des Orts- und Landschaftsschutzes erneut prüfen müssen.
Die Beschwerdeführer bestreiten, dass die Erwägungen des ersten verwaltungsgerichtlichen Entscheids vom 21. Januar 2002 in Rechtskraft erwachsen seien; rechtskräftig sei nur das Dispositiv geworden. Sie weisen darauf hin, dass auch das Verwaltungsgericht eine (teilweise) Neuprojektierung für unumgänglich erachtet habe, weshalb es die ursprüngliche ÜO und Baubewilligung auch nicht in Teilen definitiv bewilligt habe.
Die Beschwerdeführer berufen sich weiter auf den bundesgerichtlichen Entscheid vom 15. Januar 2003. Darin habe das Bundesgericht festgehalten, dass die Anpassung eines Nutzungsplans an veränderte Verhältnisse eine umfassende Interessenabwägung voraussetze; dabei dürfe nicht einfach an die Interessenabwägung der überholten bzw. anpassungsbedürftigen Planung (d.h. der ÜO Nr. 29) angeknüpft werden, sondern es müsse unter Einbezug aller raum- und umweltrelevanten Gesichtspunkte und unter Berücksichtigung der Planungsgrundsätze des RPG und der Ziele und Festlegungen des Richtplans geprüft werden, ob die weitgehend unüberbaute Alpina-Matte einer ordentlichen Bauzone, einer Sondernutzungszone oder einer Nichtbauzone zugeordnet werden solle und welche Art und welches Mass an Nutzung dort zuzulassen seien (1A.42/2002, E. 2.2.2). Mit diesen Erwägungen habe das Bundesgericht eine erneute Prüfung des Alpina-Projekts unter dem Gesichtspunkt der umfassenden raumplanerischen Interessenabwägung offen halten wollen.
Schliesslich geben die Beschwerdeführer zu bedenken, dass das Erschliessungskonzept durch den Wegfall der Norderschliessung grundlegend geändert worden sei. Diese Änderung habe eine neue umfassende raumplanerische Interessenabwägung verlangt.
3.2 Generell gilt der Grundsatz, dass nur das Dispositiv eines Entscheids in Rechtskraft erwächst, nicht aber dessen Erwägungen. Davon wird allerdings eine Ausnahme gemacht für Rückweisungsentscheide, mit denen das Gericht eine Sache zu neuer Beurteilung im Sinne ihrer Erwägungen an eine Vorinstanz zurückweist: Bei derartigen Entscheiden sind die Erwägungen des Entscheids für die Vorinstanzen verbindlich und können auch vom Gericht selbst in einem späteren Rechtsmittelverfahren nicht mehr zur Diskussion gestellt werden (zum Berner Verwaltungsprozessrecht vgl. Merkli/Aeschlimann/Herzog, Kommentar zum Gesetz über die Verwaltungsrechtspflege im Kanton Bern, Bern 1997, N 15 zu Art. 49, N 4 zu Art. 72 und N 6 zu Art. 84; zur vergleichbaren Rechtslage nach einem Rückweisungsentscheid des Bundesgerichts vgl. <ref-ruling> E. 4.2 S. 208 mit Hinweisen).
3.3 Im Entscheid vom 21. Januar 2002 hiess das Verwaltungsgericht die Beschwerden u.a. der F._ SA insofern gut, als der angefochtene Entscheid der JGK vom 29. August 2000 sowie der Gesamtentscheid des AGR vom 9. August 1999 aufgehoben und die Sache zur Überarbeitung im Sinne der Erwägungen an die Gemeinde zurückgewiesen wurde; im Übrigen wies es die Beschwerden ab (Disp.-Ziff. 1a).
Aus den Erwägungen (E. 14 S. 66) ergibt sich, dass das Hotelprojekt modifiziert werden müsse, um den Grenzabstand zur Parzelle Nr. 100 sowie (auf der westlichen Seite) die Waldabstandslinie einzuhalten. Zu überprüfen sei ferner die Terraingestaltung gegenüber der Parzelle Nr. 100 und dem Forstweg im Norden. Schliesslich müsse die Lärmsituation an der Alpinastrasse und der Palacestrasse neu beurteilt werden. Das Verwaltungsgericht hielt damals eine (teilweise) Neuprojektierung für unumgänglich, deren Umfang sich aber noch nicht absehen lasse und u.a. davon abhänge, ob die Bauherrschaft und die Gemeinde unter den neuen Voraussetzungen neue Ideen entwickeln würden. Es wies aber ausdrücklich darauf hin, dass "die Fragen und Gegenstände, die im vorliegenden Entscheid abschliessend beurteilt worden sind, nicht mehr zur Diskussion gestellt werden können". Dazu gehörten, wie sich aus den Erwägungen des damaligen Entscheids ergibt, u.a. die Zugehörigkeit des Alpina-Areals zur Bauzone (E. 4), das öffentliche Interesse und der Bedarf an der Errichtung eines neuen Luxushotels und von neuen Zweitwohnungsbauten (E. 6), der Ortsbild- und Landschaftsschutz (E. 7 und 8), die Erschliessung über die Palace- und die Alpinastrasse sowie die Nichtgenehmigung der Zweiterschliessung von Norden über die Neuretstrasse (E. 13).
Dementsprechend hielt das Verwaltungsgericht im angefochtenen Entscheid vom 22. Mai 2007 fest, dass es der Einwohnergemeinde Saanen offen gestanden hätte, eine grundsätzlich neue Planung des Alpina-Areals in Angriff zu nehmen. Da sie sich aber entschieden habe, den bereits eingeschlagenen Weg weiterzugehen, sei die JGK bei ihrem Entscheid an die Rahmenbedingungen gebunden gewesen, die das Verwaltungsgericht in seinem Urteil vom 21. Januar 2002 formuliert habe. Die gleiche Bindungswirkung komme diesem Urteil für das Verwaltungsgericht zu. Die bereits abschliessend beurteilten Fragen und Gegenstände bildeten deshalb nicht Gegenstand des verwaltungsgerichtlichen Verfahrens.
Diese Erwägungen des Verwaltungsgerichts zum Streitgegenstand entsprechen den oben dargestellten allgemeinen Grundsätzen für Rückweisungsentscheide und sind daher aus prozessualer Sicht nicht zu beanstanden.
Zwar waren die Beschwerdeführer nicht Parteien des ersten verwaltungsgerichtlichen Verfahrens. Wie bereits oben (E. 2.2.2) dargelegt worden ist, hätten sie sich jedoch am ersten Beschwerdeverfahren beteiligen können und müssen, wenn sie mit der geplanten Überbauungsordnung und dem Bauprojekt in grundsätzlicher Weise nicht einverstanden waren.
3.4 Dem stehen auch die Erwägungen des bundesgerichtlichen Entscheids vom 15. Januar 2003 nicht entgegen. In diesem Entscheid legte das Bundesgericht dar, dass der Erlass einer neuen Überbauungsordnung zur Ablösung der nur noch formell gültigen ÜO Nr. 29 keine Umgehung von Art. 24 RPG bedeute: Die Anpassung der bisherigen Planung an die durch die Sprengung des alten Alpina Hotels veränderten Umstände müsse im Wege der Planung erfolgen (E. 2.2.1), was eine umfassende Interessenabwägung voraussetze (E. 2.2.2). Diese Ausführungen bezogen sich jedoch auf das gesamte Planungsverfahren für die ÜO Nr. 56 und nicht speziell auf das Verfahren nach dem Rückweisungsentscheid des Verwaltungsgerichts vom 21. Januar 2002. Die raumplanerische Interessenabwägung der Gemeinde war bereits im verwaltungsgerichtlichen Entscheid vom 21. Januar 2002 überprüft und als rechtmässig erachtet worden. Ob diese Einschätzung zutrifft, konnte das Bundesgericht im Entscheid vom 15. Januar 2003 nicht überprüfen, weil noch kein kantonaler Endentscheid vorlag. Im vorliegenden Verfahren hätte der verwaltungsgerichtliche Entscheid vom 21. Januar 2002 grundsätzlich mitangefochten werden können, insoweit mangelt es den Beschwerdeführern aber an der formellen Beschwer (vgl. oben, E. 2.2.2). Dagegen lässt sich dem bundesgerichtlichen Entscheid vom 15. Januar 2003 nichts zum notwendigen Umfang der verwaltungsgerichtlichen Prüfung im zweiten Entscheid vom 22. Mai 2007 entnehmen.
3.5 Zu prüfen ist immerhin, ob die 2003 von der EG Saanen beschlossenen Änderungen der ÜO Nr. 56 so gewichtig waren, dass sie eine vollständig neue Interessenabwägung verlangt hätten, in der auch die Zugehörigkeit des Alpina-Areals zur Bauzone, das öffentliche Interesse und der Bedarf an der Errichtung eines neuen Luxushotels und von Zweitwohnungsbauten sowie Fragen des Ortsbild- und Landschaftsschutzes nochmals neu hätten beurteilt werden müssen.
Dies ist zu verneinen: Die Einwohnergemeinde Saanen hat die vom Verwaltungsgericht mit Urteil vom 21. Januar 2002 verlangten Änderungen vorgenommen und die Einhaltung der Plan- und Immissionsgrenzwerte für Lärm neu geprüft; dagegen hat sie keine grundlegende Änderung des Projekts vorgenommen.
Die Änderungen gegenüber dem ersten Projekt bestehen im Wesentlichen in einer Verkleinerung des Baufelds 1 auf der Ost- und der Westseite, um den Grenzabstand zur Parzelle Nr. 100 und den Waldabstand einzuhalten; dies führt zu einer gewissen Volumenreduktion des Hotels; geringfügig verkleinert wurde auch das Gebäude auf Baufeld 5. Die nicht genehmigte Norderschliessung entfällt; deshalb musste das Erschliessungskonzept für Anlieferung und Entsorgung überarbeitet werden. Dies hat Anpassungen verschiedener Baufelder zur Folge; die Hotelinfrastruktur-Bauten (Wellness, Fitness, Kinderspielraum, etc.) befinden sich neu im Baufeld 6.
Unzutreffend ist die Darstellung der Beschwerdeführer 3 und 4, wonach die geplanten Restaurants, die Bar, die vorgelagerten Chaletbauten mit Luxus-Appartements, das Hallenbad mit Wellness- und Fitnessbereich, der Kinderspielraum und die unterirdischen Einstellhallen neu seien: Diese Elemente waren alle bereits im ursprünglichen Projekt enthalten; Wellnessbereich und Hallenbad sind im geänderten Projekt lediglich etwas kleiner, dafür ist neu ein Aussenpool vorgesehen; zudem wurde die Zahl der Parkplätze verringert.
Auch die Erschliessung der Überbauung aus südlicher Richtung, über die Palacestrasse und die auszubauende Alpinastrasse, war von Anfang an vorgesehen; weggefallen ist nur die nördliche Erschliessung, die vor allem dem Baustellen-, dem Zuliefer- und Personalverkehr hätte dienen sollen. Zwar wird sich mit dem Wegfall der Norderschliessung die Lärmbelastung an der Alpina- und Palacestrasse wesentlich erhöhen; alle mit dem Zusatzverkehr der Alpina-Überbauung zusammenhängenden lärmschutzrechtlichen und raumplanerischen Aspekte wurden denn auch vom Verwaltungsgericht in seinem zweiten Entscheid ausführlich geprüft. Dagegen durfte das Verwaltungsgericht davon ausgehen, dass das aktuelle Alpina-Projekt im Übrigen mit dem Projekt aus dem Jahre 1998 übereinstimmte. Es war deshalb nicht verpflichtet, alle raumplanerischen Fragen nochmals von Grund auf zu prüfen, wie namentlich die Zuweisung des Alpina-Areals zur Bauzone und dessen Überstellung mit Hotel- und Residenzbauten. Vielmehr durfte es sich auf die 2003 beschlossenen Änderungen der ÜO beschränken, ohne das rechtliche Gehör der Beschwerdeführer zu verletzen.
3.6 Gleiches gilt für die von den Beschwerdeführern 3 und 4 gerügte Verletzung des Waldabstands: Die Beschwerdeführer machen selbst nicht geltend, dass der Abstand zum Wald durch das geänderte Projekt verkleinert worden sei. Dann aber bestand für das Verwaltungsgericht kein Grund, auf seine Erwägungen zum Waldabstand gemäss Urteil vom 21. Januar 2002 zurückzukommen. Diese können von den Beschwerdeführern mangels formeller Beschwer nicht angefochten werden.
3.7 Entsprechend verhält es sich mit der Rüge der Beschwerdeführer 3 und 4, es fehle für die geplante Verbreiterung der Alpinastrasse unter Einbezug ihrer Grundstücke an einem Enteignungstitel. Die Verbreiterung der Alpinastrasse war schon in der ersten Fassung der ÜO Nr. 56 vorgesehen und wurde 2003 nicht modifiziert. Die Beschwerdeführer hätten deshalb diese Rüge schon im Rechtsmittelverfahren gegen die ursprüngliche Überbauungsordnung ÜO Nr. 56 vorbringen müssen.
4. Die Beschwerdeführer machen weiter geltend, das Mitwirkungsverfahren für die geänderte ÜO Nr. 56 habe Art. 4 Abs. 2 RPG widersprochen. Dieses Verfahren sei erst nachträglich erfolgt, nach der Vorprüfung durch das AGR und der öffentlichen Auflage mit Einspracheverfahren. Zwischen Mitwirkung und Gemeindeversammlung hätten lediglich 14 Tage zur Verfügung gestanden. Der Mitwirkungsbericht sei unmittelbar vor der Gemeindeversammlung öffentlich bekannt gegeben worden und sei derart rudimentär verfasst gewesen, dass es nicht möglich gewesen sei, sich daraus ein angemessenes Urteil über die zur Abstimmung gebrachte Vorlage zu machen. Damit sei das Mitwirkungsverfahren zu einer blossen Alibi-Übung verkommen.
4.1 Das Verwaltungsgericht führte hierzu aus, eine Mitwirkung sei bereits im ersten Verfahren erfolgt. Mit der überarbeiteten ÜO sei aus raumplanerischer Sicht nur noch über Einzelheiten zu entscheiden gewesen, die weitgehend nur die unmittelbaren Anwohner interessiert hätten. Dies habe es gerechtfertigt, das Mitwirkungsverfahren nur in bescheidenem Rahmen und im Anschluss an die öffentliche Auflage durchzuführen. Das Verwaltungsgericht berief sich hierfür auf Art. 58 Abs. 3 Bst. c des Berner Baugesetzes vom 9. Juni 1985 (BauG), wonach es der Gemeinde erlaubt ist, die Mitwirkung im Rahmen des Einspracheverfahrens durchzuführen, wenn die ÜO nicht von allgemeinem Interesse ist.
4.2 Die Beschwerdegegnerin und die Gemeinde Saanen verweisen auf Art. 122 Abs. 1-3 der Berner Bauverordnung vom 6. März 1985 (BauV), der ein vereinfachtes Vorgehen für geringfügige Änderungen von Nutzungsplänen vorsieht, bei dem das Mitwirkungsverfahren entfällt. Dieses Verfahren habe der Gemeinderat ursprünglich einschlagen wollen, habe sich aber nach der öffentlichen Auflage für das ordentliche Verfahren entschieden. Dieses Vorgehen sei nach Art. 122 Abs. 5 BauV zulässig. Diese Bestimmung sehe ein "Zwitterverfahren" vor, wenn, wie im vorliegenden Fall, unklar sei, ob eine vorgesehene Änderung noch als geringfügig gelten könne. In diesem Fall sei das öffentliche Einspracheverfahren durchzuführen mit dem Hinweis, dass beabsichtigt sei, die Änderung im Verfahren der geringfügigen Änderung von Nutzungsplänen vorzunehmen. Kämen die Behörden nach der Auflage zum Schluss, es sei das ordentliche Verfahren durchzuführen, so springe die Zuständigkeit vom Gemeinderat wieder zurück auf die in Saanen ordentlicherweise zuständige Gemeindeversammlung, wobei das Mitwirkungsverfahren notwendigerweise "leide".
4.3 Art. 4 Abs. 2 RPG schreibt vor, dass die mit Planungsaufgaben betrauten Behörden dafür sorgen, dass die Bevölkerung bei Planungen in geeigneter Weise mitwirken kann. Über die konkrete Ausgestaltung der Mitwirkung entscheidet der kantonale Gesetzgeber (Rudolf Muggli, RPG-Kommentar, N 27 zu Art. 4).
Im Kanton Bern ist das Mitwirkungsverfahren in Art. 58 BauG näher geregelt. Dieser lautet:
Art. 58 BauG Information und Mitwirkung der Bevölkerung
1 Die Behörden sorgen dafür, dass die Bevölkerung bei Planungen frühzeitig in geeigneter Weise mitwirken kann.
2 Für den Erlass und die nicht geringfügige Änderung von Richtplänen, der baurechtlichen Grundordnung und von Überbauungsordnungen ist die Mitwirkung zu gewähren. [...]
3 Die Mitwirkung kann eingeräumt werden,
a indem vorgesehene Planungen an der Gemeindeversammlung oder an besonderen Orientierungsversammlungen zur Diskussion gestellt werden;
b indem die Unterlagen über vorgesehene Planungen während einer angemessenen Mitwirkungsfrist öffentlich aufgelegt werden;
c bei vorgesehenen Änderungen der Grundordnung oder einer Überbauungsordnung, die nicht von allgemeinem Interesse sind, auch im Rahmen des Einspracheverfahrens nach Artikel 60.
4 Im Rahmen der Mitwirkung können Einwendungen erhoben und Anregungen unterbreitet werden. Sie sind den für Beschluss und für Genehmigung zuständigen Behörden in Form des Versammlungsprotokolls oder eines zusammenfassenden Mitwirkungsberichtes zur Kenntnis zu bringen. Protokoll und Bericht sind öffentlich.
[...]
Bei geringfügigen Änderungen von Nutzungsplänen findet ein vereinfachtes Verfahren statt, das in Art. 122 BauV geregelt ist. Dieser lautet:
Art. 122 BauV Geringfügige Änderung von Nutzungsplänen
1 Der Gemeinderat kann die geringfügige Änderung von Vorschriften und Plänen ohne Vorprüfung und ohne öffentliche Auflage beschliessen.
. [...].
. [...].
. [...].
5 Ist zweifelhaft, ob eine vorgesehene Änderung noch als geringfügig gelten kann, so ist für sie das öffentliche Einspracheverfahren nach Artikel 60 des Baugesetzes durchzuführen mit dem Hinweis, dass beabsichtigt ist, die Änderung im Verfahren der geringfügigen Änderung von Nutzungsplänen vorzunehmen.
Die Beschwerdeführer machen nicht geltend, dass diese gesetzliche Ordnung Art. 4 Abs. 2 RPG widersprechen würde oder sich aus Bundesrecht weitergehende Mitwirkungsrechte ergeben würden; dies ist auch nicht ersichtlich (vgl. Muggli, a.a.O., N 12 und 25 zu Art. 4 RPG zur Möglichkeit, die Mitwirkung für untergeordnete Planänderungen ohne öffentliches Interesse auszuschliessen).
4.4 Im vorliegenden Fall ist die aus Sicht der Allgemeinheit entscheidende Mitwirkung bereits im Rahmen des ersten Verfahrens 1997/1998 erfolgt, in dem die Bevölkerung frühzeitig und umfassend an der Planung mitwirken konnte. Nach dem Rückweisungsentscheid des Verwaltungsgerichts beschränkte sich die Gemeinde darauf, in Absprache mit der Bauherrschaft die gerichtlich festgestellten Mängel zu beseitigen, ohne die Planung in ihren Grundzügen zu ändern (vgl. oben, E. 3.5). Die Änderungen waren vor allem für die unmittelbar angrenzenden Nachbarn von Bedeutung, nicht aber von allgemeinem Interesse. Dies belegen auch die (wenig zahlreichen) Eingaben im Mitwirkungsverfahren, die alle von Anwohnern der näheren Umgebung und überwiegend von Einsprechern stammen.
Insofern wäre es bundesrechtlich nicht zu beanstanden gewesen, wenn die gebotene Mitwirkung im Rahmen des Einspracheverfahrens gewährt worden wäre, wie dies Art. 58 Abs. 3 lit. c BauG zulässt. Dann aber kann der Einwohnergemeinde Saanen nicht vorgeworfen werden, dass sie mehr getan hat, indem sie nach dem Einspracheverfahren noch ein Mitwirkungsverfahren durchführte, auch wenn die Zeit hierfür knapp bemessen war (Auflage vom 29. Oktober bis 28. November 2003) und der Mitwirkungsbericht erst unmittelbar vor der Gemeindeversammlung veröffentlicht wurde. Unbegründet erscheint auch die Kritik am Inhalt des Mitwirkungsberichts: Dieser fasst den wesentlichen Inhalt der Eingaben zusammen und nimmt zu jedem Punkt Stellung.
5. Die Beschwerdeführer hatten vor Verwaltungsgericht den Beizug der Akten der Ortsplanungsrevision Saanen 2005-2008 beantragt. Das Verwaltungsgericht wies diesen Antrag ab, weil die Beschwerdesache nach dem zur Zeit der Einreichung des Baugesuchs geltenden Recht zu beurteilen sei (Art. 36 Abs. 1 BauG) und damit aufgrund der in jenem Zeitpunkt und auch heute noch geltenden bau- und planungsrechtlichen Grundordnung.
5.1 Die Beschwerdeführer machen dagegen geltend, es sei nicht nur ein Baugesuch, sondern auch eine Überbauungsordnung und damit eine Planung zu beurteilen. Es widerspreche elementaren Grundsätzen der Raumplanung, mit einer vorgezogenen Einzeleinzonung die zukünftige Ortsplanungsrevision vorwegzunehmen bzw. zu präjudizieren. Dies habe das AGR mit Entscheid vom 4. April 2005 betreffend die ÜO Nr. 64 "Alpenblick" Gstaad richtig festgestellt. Gleiches müsse aber auch für die vorliegend streitige Überbauungsordnung gelten: Eine vorweggenommene Einzeleinzonung sei nur zulässig, wenn bereits ein konsolidiertes Gesamtkonzept (räumliches Leitbild) die Umzonung vorsehe und daher das Gesamtergebnis der Ortsplanungsrevision nicht vorweggenommen werde. Die Gemeinde Saanen verfüge noch nicht über ein solches Leitbild. Die Planungsarbeiten für die ÜO Nr. 56 hätten deshalb mit der laufenden Ortsplanungsrevision koordiniert werden müssen.
5.2 Die Beschwerdegegnerin und die Gemeinde Saanen wenden dagegen ein, die Ortsplanungsrevision befinde sich noch in der ersten Phase der Mitwirkung und es werde noch lange dauern, bevor die zuständigen Planungsbehörden verbindliche Beschlüsse fällen könnten. Der Vergleich mit dem "Alpenblick" hinke, weil es dort um eine Neueinzonung gegangen sei.
5.3 Die Überbauungsordnung Nr. 56 wurde 1998 erstmals beschlossen, auf der Grundlage der 1993 revidierten und am 1994 genehmigten Ortsplanung. Zum damaligen Zeitpunkt war keine weitere Ortsplanungsrevision hängig, die hätte berücksichtigt werden müssen. Nach der Rückweisung der Sache durch das Verwaltungsgericht im Jahr 2003 war die Gemeinde an die Vorgaben des Verwaltungsgerichts gebunden; danach war die Zugehörigkeit des Alpina-Areals zur Bauzone und dessen Nutzung für Hotel- und Residenzbauten bereits verbindlich entschieden (vgl. oben, E. 3.3). Im neuen Verfahren beschränkte sich die Gemeinde darauf, die vom Verwaltungsgericht beanstandeten Rechtswidrigkeiten zu beheben (vgl. oben, E. 3.5). Hierfür bedurfte es keines konsolidierten Gesamtkonzepts oder räumlichen Leitbilds. Insofern ist nicht zu beanstanden, dass weder das Verwaltungsgericht noch die Vorinstanzen die Unterlagen zur hängigen Ortsplanungsrevision eingeholt haben.
6. Das Verwaltungsgericht ging davon aus, dass das Bauvorhaben unter Berücksichtigung der neu erstellten Lärmschutzwand beim Chalet Viola die für die Empfindlichkeitsstufe (ES) II massgebenden Planungswerte für Strassenverkehrslärm von 55 dB(A) am Tag und von 45 dB(A) in der Nacht bzw. die massgebenden Immissionsgrenzwerte von 60 dB(A) am Tag und von 50 dB(A) in der Nacht einhalten könne. Es stützte sich hierfür auf das amtliche Lärmgutachten der Planteam GHS AG (im Folgenden: Planteam) vom 15. März 2005 sowie dessen Aktualisierung vom 6. Oktober 2006.
Die Beschwerdeführer machen dagegen geltend, der vom Alpina-Projekt zu erwartende Mehrverkehr sei offensichtlich unrichtig festgestellt worden. Bei realistischer Einschätzung des nächtlichen Verkehrsaufkommens werde der Planungswert an der Alpinastrasse und der Immissionsgrenzwert an der Palacestrasse nachts klar überschritten.
6.1 Das Verwaltungsgericht wendete die Art. 25 und 11 Abs. 3 USG auch für den von der Überbauung verursachten Strassenverkehrslärm auf den Zufahrtsstrassen (Alpina- und Palacestrasse) an. Es verlangte deshalb, dass die von der Alpina-Überbauung allein erzeugten Verkehrslärmimmissionen die Planungswerte in der Umgebung nicht überschreiten, und der durch die Überbauung verursachte Verkehr zusammen mit dem bestehenden Verkehr die Immissionsgrenzwerte des Anhangs 3 zur LSV einhält. Diese rechtliche Würdigung wird von den Parteien nicht beanstandet.
6.2 Die Beschwerdeführer bestreiten die dem amtlichen Lärmgutachten zugrundeliegenden Prognosen zum künftigen Mehrverkehr des Alpina-Projekts. In diesem Punkt habe der amtliche Gutachter die Prognosen des Parteigutachtens "P+ Petermann Philippin" (im Folgenden: P+) vom 30. April 2003 übernommen, ohne diese abzuklären und näher zu begründen; dies sei auch im Ergänzungsgutachten vom 6. Oktober 2006 nicht geschehen. Dennoch habe das Verwaltungsgericht die Annahmen für plausibel gehalten und sich mit den dagegen vorgebrachten Einwendungen der Beschwerdeführer nicht auseinandergesetzt, mit dem Hinweis, diese seien nicht genügend substanziiert. Damit habe das Verwaltungsgericht die Regeln über die Beweispflicht, <ref-law> und die Begründungspflicht verletzt.
Die Beschwerdeführer rügen insbesondere die Prognosen für die durchschnittlichen Fahrtenbewegungen in der Nacht (22.00 bis 6.00 Uhr). Das amtliche Gutachten gehe von durchschnittlich 9 Fahrzeugen pro Stunde (Fz/h) für den gesamten Hotelbetrieb aus. Dabei sei insbesondere der Mehrverkehr, der durch auswärtige Restaurantbesucher verursacht werde, krass unterschätzt worden. Bereits die Prognose von durchschnittlich 100 externen Restaurantgästen pro Tag sei zu niedrig. Offensichtlich falsch sei sodann die Annahme, das Verhältnis der Restaurantbesuche zwischen Tag und Nacht betrage 94:6. In Gstaad seien die Restaurants vor allem abends besetzt, und zwar auch durch auswärtige Besucher und Gäste. Hinzu komme noch der Verkehr von auswärtigen nächtlichen Bar-Besuchern. Die Bauherrschaft habe um eine generelle Überzeitbewilligung für die Bar von 22.00 bis 3.30 Uhr ersucht. Es sei einleuchtend, dass ein Etablissement, das bis 3.30 Uhr in der Frühe Gäste bewirte, überdurchschnittlichen nächtlichen Verkehr verursachen werde. Dennoch sei Planteam ohne Begründung von einem unterdurchschnittlichen nächtlichen Verkehrsaufkommen von 6 % (gegenüber 7 % im schweizerischen Durchschnitt) ausgegangen.
Nicht berücksichtigt worden sei ferner der Verkehr durch Kongresse, Seminare usw. sowie durch externe Gäste des Hallenbads und Wellness-Bereichs. Auch der Betriebsverkehr und der Verkehr der hotelmässig bewirtschafteten Appartements seien zu niedrig veranschlagt worden. Schliesslich sei das vom Gutachten Planteam zugrunde gelegte spezifische Motorfahrzeugfahrten-Potenzial von 1 (jeder Gast verursacht pro Tage nur eine Zu- oder Wegfahrt) weltfremd.
Die vom Verwaltungsgericht angenommenen "Sicherheitsmargen" würden daran nichts ändern: Die verfügte Geschwindigkeitsbegrenzung von 30 km/h sei bereits im Gutachten Planteam berücksichtigt worden; die vom Gutachten Planteam zugrundegelegte und vom Verwaltungsgericht als sehr hoch beurteilte Belegung der Hotelzimmer mit 70 % habe kaum Auswirkungen auf den nächtlichen Verkehr.
Die Beschwerdeführer weisen auf die Berechnungen des aktualisierten amtlichen Gutachtens hin, wonach schon bei einem nächtlichen Zusatzverkehr von mehr als 11 Fz/h der Planungswert am Punkt 3 der Alpinastrasse überstiegen werde. Dies bedeute, dass der Planungswert bereits überschritten sei, wenn der von Planteam prognostizierte nächtliche Durchschnittsverkehr um mehr als 2 Fz/h nach oben korrigiert werden müsse.
6.2.1 Gemäss <ref-law> kann die Feststellung des Sachverhalts nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 BGG beruht. Grosse Zurückhaltung erlegt sich das Bundesgericht insbesondere bei der Überprüfung von Verkehrsprognosen auf, die zwangsläufig mit beträchtlichen Unsicherheiten verbunden sind (<ref-ruling> E. 12 S. 322 mit Hinweis).
Wie das Verwaltungsgericht zutreffend ausgeführt hat, trägt das Risiko einer Fehlprognose die Bauherrschaft: Sollte sich bei späteren Messungen herausstellen, dass die Belastungsgrenzwerte nicht eingehalten sind, so werden Anordnungen zu treffen sein, um die Lärmimmissionen aus dem Betrieb des Hotels Alpina mit Massnahmen an der Quelle zu reduzieren. Dies gilt auch ohne einen ausdrücklichen dahingehenden Vorbehalt in der Baubewilligung (<ref-ruling> E. 2.4 S. 39).
6.2.2 Nach Rückweisung der Sache an die Gemeinde durch das Verwaltungsgericht wurden umfangreiche Abklärungen zur Lärmbelastung vorgenommen: Die Bauherrschaft reichte das Gutachten P+ vom 30. April 2003 (mit Ergänzungen vom 23. September 2003) zum Nachweis der Einhaltung der Belastungsgrenzwerte ein. Die Beschwerdeführer bestritten dessen Prognosen unter Berufung auf einen von ihnen in Auftrag gegebenen Bericht der Firma Ecosens AG/Tensor Umweltberatung AG (im Folgenden: Ecosens/Tensor) vom 30. Juli 2003. Daraufhin beauftragte die JGK die Planteam GHS AG mit der Erstellung eines neuen Gutachtens betreffend Verkehrs- und Lärmprognosen sowie Verkehrssicherheit (Gutachten vom 15. März 2005). Hierzu reichten die Beschwerdeführer einen Zusatzbericht Ecosens/Tensor vom 10. Mai 2005 ein. Vor Verwaltungsgericht wurden weitere ergänzende Stellungnahmen zu den Akten gegeben (Zusatzbericht Ecosens/Tensor vom 29. November 2005; Stellungnahme P+ zum Bereich Lärm vom 6. Januar 2006; Messtechnische Überprüfung P+ vom 23. Mai 2006 zur Wirkung der Lärmschutzwand an der Palacestrasse). Auf der Grundlage dieser Gutachten und Stellungnahmen holte das Verwaltungsgericht das aktualisierte Gutachten Planteam vom 6. Oktober 2006 ein.
Das BAFU kommt in seiner Vernehmlassung zum Ergebnis, das Gutachten Planteam (samt Aktualisierung) entspreche den massgebenden Bestimmungen der LSV über die Ermittlung und Beurteilung von Strassenlärm. Die Berechnungen und die durchgeführten Lärmmessungen seien korrekt und würden gut und nachvollziehbar dokumentiert. Sie seien gemäss dem aktuellen Stand der Technik erfolgt. Die Verkehrsannahmen sowie die künftigen Betriebszahlen erachtet das BAFU als plausibel.
6.2.3 Das Gutachten Planteam basiert auf folgenden Annahmen:
- -:-
- -:-
- Belegung mit durchschnittlich 209 Gästen täglich, davon 35 in Appartements, 74 im Hotel und 100 externe Personen in der Restaurants;
- Hotelbetrieb mit durchschnittlich 100 Angestellten und 15 Betriebsparkplätzen;
- spezifisches Motorfahrzeugfahrten-Potenzial vom 1.0 pro Gast, 0.25 pro Angestellten, 11.42 pro Betriebsparkplatz und 0.2 für die Versorgung pro Appartement- und Hotelgast;
- durchschnittlicher täglicher Zusatzverkehr (DTV) von 427 Fahrten über 24 Stunden;
- Zusatzverkehr am Tag von durchschnittlich 22 Fahrten pro Stunde und einem akustischen Schwerverkehrsanteil von 5 %;
- Zusatzverkehr in der Nacht von durchschnittlich 9 Fahrten pro Stunde und einem akustischen Schwerverkehrsanteil von 3 %;
- Geschwindigkeitsbegrenzung auf der Palacestrasse von 50 km/h und auf der Alpinastrasse von 30 km/h.
Diese Annahmen wurden nicht ungeprüft vom Gutachten P+ übernommen. Vielmehr stellte Planteam die Annahmen P+ denjenigen von Ecosens/Tensor gegenüber und kam zum Ergebnis, die Fahrtenberechnung des Gutachtens P+ sei in der Grundlage plausibel. Die angenommenen Fahrtenzahlen seien grosszügig berechnet und dürften in der Realität tiefer anzusetzen sein. Einzig die Fahrtenzahlen der Versorgung pro Gast am Tag seien eher zu tief angesetzt; diese Zahlen wurden deshalb von Planteam nach oben korrigiert. Dagegen könne während der Nachtperiode von den Angaben P+ ausgegangen werden.
6.2.4 Auch das Verwaltungsgericht hielt diese Zahlen für plausibel. Es berief sich auf das betriebswirtschaftliche Gutachten der Firma Bruppacher & Partner vom 19. November 2003, wonach die durchschnittliche Zimmerauslastung der drei bestehenden Luxushotels in der Region Gstaad-Saanenland in den Jahren 1998-2002 bei 42 % lag, die durchschnittliche Bettenauslastung bei 37 %. Zudem sei zu berücksichtigen, dass inzwischen mit dem renovierten Grand Hotel Bellevue in Gstaad ein viertes Luxushotel in der Region geführt werde. Dem Verwaltungsgericht erschien deshalb die von P+ zugrundegelegte durchschnittliche Hotelauslastung von 70 % deutlich zu hoch angesetzt; in der Realität dürften die Fahrtenzahlen tiefer anzusetzen sein.
6.2.5 Diese Einschätzung wird durch den im Gutachten P+ vom 30. April 2003 (Ziff. 2.6.2 S. 11) angestellten Vergleich zwischen dem geschätzten Verkehrsaufkommen des Alpina und dem gezählten Verkehrsaufkommen des Palace Hotels bestätigt. Dieser Vergleich zeigt, dass die Verkehrsannahmen beim Alpina deutlich höher liegen als das Verkehrsaufkommen des Palace, obwohl die Betriebsdaten (Hotelbetten, Appartements, Arbeitsplätze) beim Palace grösser sind als beim Alpina. Die Beschwerdeführer wenden dagegen ein, dieser Vergleich berücksichtige die Nebenbetriebe (Restaurants, Hallenbad, Konferenzräume, Bars) nicht; sie legen aber nicht dar, inwiefern sich die Ausstattung des Palace Hotels und des geplanten Alpina Hotel unterscheiden und das Verkehrsaufkommen deshalb nicht vergleichbar sei.
6.2.6 Auch die von Planteam und P+ zugrundegelegten spezifischen Motorfahrzeugfahrten-Potenziale (SMfzP) können nicht als offensichtlich falsch erachtet werden. In der Stellungnahme Ecosens/Tensor vom 10. Mai 2005 (S. 2 oben) wird eingeräumt, dass die Potenziale von Gastbetrieben je nach Lage, Umgebung, Art der Kunden und des Angebots in weiten Bereichen variieren können und sich kaum Erfahrungswerte in der Literatur finden. Unter diesen Umständen ist ein SMfzP von 1 pro Hotel- und Appartement - unter der Annahme, dass einige Hotelgäste ein Auto zu zweit oder zu mehreren benutzen oder sich auch zu Fuss oder mit dem Gästebus bewegen werden (Gutachten P+ vom 30. April 2003 S. 10) - nicht zu beanstanden.
6.2.7 Näher zu prüfen ist deshalb nur der von den Beschwerdeführern als offensichtlich zu niedrig beanstandete Anteil von Nachtfahrten. Diese Zahl hängt vor allem von der Anzahl externer Restaurant- und Barbesucher ab. Das amtliche Gutachten Planteam geht, wie schon das Gutachten P+, von durchschnittlich 9 Fahrten pro Stunde für den Nachtzeitraum (22.00 bis 6.00 Uhr) aus; dies unter der Annahme, dass die auf durchschnittlich 100 täglich geschätzten externen Restaurantgäste 94 Fahrten zur Tageszeit (vor 22.00 Uhr) und nur 9 Fahrten zur Nachtzeit verursachen. Dies wird von den Beschwerdeführern als offensichtlich falsch erachtet.
Auch in dieser Hinsicht ist ein Vergleich mit den auf der Zufahrt zum Palace Hotel gezählten Verkehrsbewegungen aufschlussreich: Dort wurde ein durchschnittlicher nächtlicher Verkehr von nur 2 Fz/h gezählt (Gutachten P+ vom 30. April 2003 S. 6). Auch wenn man berücksichtigt, dass diese Zählung im Oktober, ausserhalb der Hochsaison, und an einem Wochentag durchgeführt wurde, erscheint die Schätzung von 9 Fz/Nachtstunde für das Alpina im Vergleich plausibel, handelt es sich doch um eine Durchschnittszahl über das ganze Jahr und sämtliche Nachtstunden hinweg. Hinzuweisen ist auch auf die von Planteam vorgenommene Verkehrszählung während der sommerlichen Hochsaison Ende Juli 2006, die deutlich weniger Fahrzeuge im massgebenden Nachtzeitraum ergeben hat (16 Fz/h) als im Gutachten vom 15. März 2005 für den bestehenden Verkehr im Jahresdurchschnitt berechnet worden waren (38 Fz/h; vgl. Aktualisierung vom 6. Oktober 2006 S. 8).
Der Einwand der Beschwerdeführer, der von Planteam angenommene Anteil des nächtlichen Verkehrs (zwischen 22.00 und 6.00 Uhr) liege mit 6 % noch unter dem schweizerischen Durchschnitt von 7 %, ist unzutreffend: Tatsächlich beträgt das prognostizierte Verkehrsaufkommen in der Nacht zwischen 10-20 % des Gesamtverkehrs und entspricht damit in etwa dem von Ecosens/Tensor (Stellungnahme vom 10. Mai 2005 S. 2) vorgeschlagenen Anteil (vgl. ergänzende Stellungnahme P+ vom 6. Januar 2006 S. 5 Ziff. 2.3).
6.2.8 Die prognostizierten Zahlen könnten sich dennoch als zu niedrig erweisen, sollten die Restaurants und Bars des Alpina zahlreiche externe Besucher zur Abend- und Nachtzeit anziehen. Dies lässt sich derzeit aber nicht seriös abschätzen. Auch die von Ecosens/Tensor geschätzten Besucherzahlen beruhen lediglich auf Annahmen, die nicht plausibler erscheinen als diejenigen von Planteam und P+. Insbesondere die von Ecosens/Tensor (Stellungnahme vom 10. Mai 2005 S. 1) angenommene Auslastung des Hotelrestaurants mit 100 % am Abend erscheint - als jährlicher Durchschnittswert - unrealistisch hoch.
Der Verkehr durch externe Gäste der Konferenzräume, des Hallenbads, Fitness, usw. ist nicht in der Nacht, sondern tagsüber zu erwarten, d.h. zu einem Zeitpunkt, in dem die Belastungsgrenzwerte klar eingehalten werden.
6.2.9 Nach dem Gesagten durfte das Verwaltungsgericht auf die Prognosen des amtlichen Gutachters abstellen, ohne Bundesrecht zu verletzen.
6.3 Weiter rügen die Beschwerdeführer, der zu erwartende Mehrverkehr an der Palacestrasse durch künftige Bauprojekte sei falsch abgeschätzt worden; die Beschränkung auf 29 Wohneinheiten mit dem Argument, bestehende Bauparzellen würden zum Schutz der Aussicht nicht überbaut, sei unglaubwürdig.
Dem ist entgegenzuhalten, dass <ref-law> die Zu- oder Abnahme der Lärmimmissionen durch die Errichtung, Änderung oder Sanierung ortsfester Anlagen nur dann verlangt, wenn diese mit einer gewissen Wahrscheinlichkeit zu erwarten ist, insbesondere wenn entsprechende Projekte im Zeitpunkt der Ermittlung bereits bewilligt oder öffentlich aufgelegt worden sind. Im vorliegenden Fall ermittelte das Gutachten Planteam vom 15. März 2005 (S. 10 Ziff. 2.3), dass auf den zehn unüberbauten Parzellen mit Zufahrt über die Palacestrasse maximal 29 Wohneinheiten erstellt werden könnten; es nahm aber an, dass ein Teil der Parzellen offenbar zur Sicherstellung der Aussicht dienten, deren Überbauung also ungewiss sei. Dies ist nicht zu beanstanden, sofern noch keine konkreten Bauprojekte für diese Parzellen bekannt sind.
Das Gutachten Planteam verzichtete auf eine Abschätzung des durch die künftige Überbauung zu erwartenden Mehrverkehrs, weil dieser die Strassenverkehrslärmbelastung nur geringfügig erhöhen dürfte und deshalb innerhalb der Prognosesicherheit liege. Dies verstösst nicht gegen Bundesrecht, bestehen doch bei der Palacestrasse (im Gegensatz zur Alpinastrasse) Reserven für die Einhaltung der nächtlichen Belastungsgrenzwerte: Nach dem aktualisierten Gutachten Planteam vom 6. Oktober 2006 (S. 10 Ziff. 2.3, Lärmprognose mit variablem Zusatzverkehr) könnte der massgebende Immissionsgrenzwert erst bei einem nächtlichen Verkehr von über 55 Fz/h (anstatt der prognostizierten 46 Fz/h) nicht mehr eingehalten werden.
7. Die Beschwerdeführer beanstanden ferner die raumplanerische Interessenabwägung im Zusammenhang mit der Erschliessung. In diesem Zusammenhang machen sie geltend, das hochsaisonale Verkehrsaufkommen wie auch der zukünftige Verkehr im Oberbortquartier sei nicht ausreichend abgeklärt und berücksichtigt worden. Das Projekt stelle einen empfindlichen Eingriff in die Wohn- und Erholungsqualität des Oberbortquartiers dar und diene einseitig den Partikulärinteressen der Beschwerdegegnerin. Wenn überhaupt, dann sollte das Projekt an einem anderen Standort realisiert werden.
7.1 Das Verwaltungsgericht führte dazu aus, der massgebende Anh. 3 zur LSV kenne keine Belastungsgrenzwerte für Spitzenbelastungen, sondern stelle auf den durchschnittlichen Tages- und Nachtverkehr im Jahresmittel ab (Anh. 3 Ziff. 32 Abs. 1 LSV). Hochsaisonale Spitzenbelastungen seien deshalb nicht im Rahmen der lärmschutzrechtlichen Beurteilung zu berücksichtigen, sondern im Rahmen der raumplanerischen Interessenabwägung, sollen doch nach dem Planungsgrundsatz von Art. 3 Abs. 3 lit. b RPG Wohngebiete vor schädlichen und lästigen Einwirkungen möglichst verschont werden. Hierfür seien in erster Linie Erschliessungsalternativen zu prüfen. Angesichts der Nichtgenehmigung der Zweiterschliessung ab der Neuretstrasse stehe keine andere Erschliessungsvariante zur Diskussion. Auch wenn die hochsaisonalen Spitzenbelastungen mit Verkehrslärm im Bereich der Palacestrasse und der Alpinastrasse raumplanungsrechtlich nicht unproblematisch erscheinen, komme die Verweigerung der Planung nicht in Betracht, da den entsprechenden Perioden über das ganze Jahr betrachtet längere Zeitabschnitte gegenüberstünden, in denen das Verkehrsaufkommen klein sei und relative Ruhe herrsche. In diesem Zusammenhang verwies das Verwaltungsgericht auf das Gutachten Planteam, das von 17 Spitzenwochen, 11 Flautenwochen und 24 übrigen Wochen ausging. Einer ausgesprochenen Tourismusgemeinde stehe es im Rahmen ihrer Planungsautonomie zu, darüber zu befinden, welche Art von Tourismus sie zu entwickeln gedenke.
7.2 Diese Erwägung ist aus Sicht des Bundesrechts nicht zu beanstanden. Zwar benutzen die Beschwerdeführer ihre Ferienchalets vorwiegend in der Hochsaison und werden deshalb vom hochsaisonalen Verkehrsaufkommen besonders betroffen, ohne von den ruhigen Zeiten zu profitieren. Diese Entwicklung könnte sich noch verstärken, wenn das Oberbortquartier verdichtet überbaut werden sollte, wie dies die Beschwerdeführer befürchten. Es ist jedoch in erster Linie Sache der Gemeinde zu entscheiden, ob sie ihre touristische Entwicklung durch den Bau weiterer Hotel- und Zweitwohnungsbauten forcieren will, auch wenn dies zur Folge hat, dass Gstaad für Personen, die Ruhe und Erholung suchen, unattraktiv wird. Schonendere Erschliessungsalternativen sind nicht ersichtlich und werden auch von den Beschwerdeführern nicht vorgeschlagen. Der Standort der Alpina-Überbauung selbst stand, wie bereits oben (E. 3) dargelegt wurde, im (zweiten) Verfahren vor Verwaltungsgericht nicht mehr zur Diskussion und kann auch im vorliegenden Verfahren nicht mehr überprüft werden (vgl. oben, E. 2.2.2).
8. Nach dem Gesagten erweist sich die Beschwerde als unbegründet, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer grundsätzlich kostenpflichtig und müssen die Beschwerdegegnerin für die Kosten des bundesgerichtlichen Verfahrens entschädigen (Art. 65 f. und <ref-law>), wobei die in ihrem amtlichen Wirkungskreis handelnde Gemeinde keine Parteientschädigung beanspruchen kann (<ref-law>).
Hinsichtlich der Kostenfolgen machen die Beschwerdeführer 3 und 4 allerdings geltend, das Verhalten der Beschwerdegegnerin und der Gemeinde Saanen, die im Laufe des kantonalen Verfahrens eine Lärmschutzwand beim Chalet "Viola" an der Palacestrasse erstellt hätten, sei als teilweises Unterziehen unter die Begehren der Beschwerdeführer zu würdigen. Wie es sich damit verhält, kann jedoch offen bleiben.
Der Bau der Lärmschutzwand erfolgte bereits im kantonalen Verfahren, vor dem Entscheid des Verwaltungsgerichts. Dieser Umstand wäre daher - wenn überhaupt - bei der Kostenverteilung im verwaltungsgerichtlichen Verfahren zu berücksichtigen gewesen. Der Kostenentscheid des Verwaltungsgerichts wurde jedoch von den Beschwerdeführern nicht selbständig angefochten; die zitierten Ausführungen zum "Unterziehen" befinden sich auch nicht in der - für die Beschwerdebegründung massgeblichen - Beschwerdeschrift, sondern in einer späteren Stellungnahme.
Unter diesen Umständen besteht kein Grund, den kantonalen Kostenentscheid aufzuheben oder die Kosten im bundesgerichtlichen Verfahren abweichend vom Unterliegerprinzip zu verteilen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerden werden abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 8'000.-- werden zur Hälfte (Fr. 4'000.--) den Beschwerdeführern des Verfahrens 1C_176/2007 (A._ AG und B._) und zur Hälfte den Beschwerdeführern des Verfahrens 1C_177/2007 (C._ und D._) auferlegt.
3. Die Beschwerdeführer des Verfahrens 1C_176/2007 (A._ AG und B._) haben die E._ AG mit insgesamt Fr. 4'000.-- für das bundesgerichtliche Verfahren zu entschädigen; sie haften zu gleichen Teilen und unter solidarischer Haftung.
4. Die Beschwerdeführer des Verfahrens 1C_177/2007 (C._ und D._) haben die E._ AG mit insgesamt Fr. 4'000.-- für das bundesgerichtliche Verfahren zu entschädigen; sie haften zu glei chen Teilen und unter solidarischer Haftung.
5. Dieses Urteil wird den Parteien, der Einwohnergemeinde Saanen, der Justiz-, Gemeinde- und Kirchendirektion, dem Verwaltungsgericht des Kantons Bern, Verwaltungsrechtliche Abteilung, dem Bundesamt für Umwelt und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 24. Januar 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber