Sachverhalt:
A. X._ sind Eigentümer des Grundstücks 1643 im Halte von 19'795 m2 im Gebiet Tellenmatt/Bröchli in der Stadtgemeinde Zug, oberhalb der SBB-Linie Zug-Arth-Goldau. Sie sind auch Eigentümer der Grundstücke 3734 und 3806 unterhalb der Bahnlinie.
Im Zonenplan 1982 war das Gebiet entlang der Eisenbahnlinie (Tellenmatt/Bröchli) mit der Parzelle 1643 einer Wohnzone W21⁄2 zugewiesen. Das oberhalb und nördlich davon gelegene Gebiet Gimenen lag in der Einfamilienhauszone E11⁄2. Der südliche und östliche Teil des Gimenen-Gebiets war einer der späteren Planung vorbehaltenen Zone (SPV-Zone) zugewiesen.
Am 2. November 1989 reichte ein Initiativkomitee bei der Stadt Zug die "Volksinitiative zum Schutz unserer Grünflächen vor Zersiedlung" (Grünflächen-Initiative) ein. Diese verlangte u.a., dass 80% der SPV-Zonen und 60% der unüberbauten und nicht als Bauland erschlossenen Wohnzonen mit tiefer Ausnützungsziffer (E11⁄2, E21⁄2, W21⁄2) der Landwirtschaftzone zugewiesen würden. Die Initiative wurde am 24. Juni 1990 von den Stimmbürgern angenommen. Daraufhin erliess der Regierungsrat am 24. September 1990 eine Planungszone über das Gebiet Tellenmatt/Bröchli/Gimenen.
Im Rahmen einer umfassenden Ortsplanungsrevision beschloss der Gemeinderat der Stadt Zug am 30. August 1994 eine neue Bauordnung mit Zonenplan, die in der Urnenabstimmung vom 4. Dezember 1994 gutgeheissen und vom Regierungsrat am 4. Juli 1995 genehmigt wurde. Das zwischen Zug und Oberwil gelegene Gebiet "Gimenen/ Brüchli/Tellenmatt" mit dem Grundstück 1643 wurde der Landwirtschaftszone zugewiesen. Die dagegen erhobene Beschwerde von X._ wurde am 8. Januar 1998 vom Verwaltungsgericht des Kantons Zug abgewiesen.
B. Am 25. Januar 2008 reichten X._ ein Entschädigungsbegehren gegen die Einwohnergemeinde der Stadt Zug wegen materieller Enteignung in Höhe von Fr. 23'951'680.-- nebst Zins seit 28. Januar 1998 ein.
Die Schätzungskommission stellte mit Zwischenentscheid vom 23. Juni 2008 fest, dass die von den Gesuchstellern geltend gemachten Entschädigungsansprüche nicht verjährt seien.
Am 24. August 2009 führte die Schätzungskommission einen Augenschein durch, hörte die Parteien an und befragte Auskunftspersonen. Am 26. November 2009 stellte sie fest, dass die Nichteinzonung des Grundstücks 1643 durch den Zonenplan 1995 der Gemeinde Zug eine materielle Enteignung bewirke. Sie sprach den Gesuchstellern hierfür eine Entschädigung von Fr. 15'440'100.-- sowie Fr. 157'700.70 für nutzlos aufgewendete Planungskosten zu, nebst Zinsen ab 1. Februar 1998.
C. Gegen den Schätzungsentscheid erhoben sowohl die Einwohnergemeinde der Stadt Zug als auch die Eheleute X._ Beschwerde beim Verwaltungsgericht des Kantons Zug. Die Stadt Zug schloss auf vollumfängliche Abweisung des Entschädigungsgesuchs, während die Eheleute X._ beantragten, es sei festzustellen, dass auch eine Auszonung des Grundstücks 1643 vorliege, die eine materielle Enteignung bewirke; die Entschädigung sei auf Fr. 980.-- pro m2, d.h. auf total Fr. 19'399'100.--, festzulegen.
Am 27. März 2012 hiess das Verwaltungsgericht die Beschwerde der Stadt Zug gut und stellte fest, dass den Eigentümern des Grundstücks 1643 kein Entschädigungsanspruch aus materieller Enteignung zustehe. Die Beschwerde der Eheleute X._ wies es ab.
D. Gegen diesen Entscheid haben X._ am 14. Mai 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und es sei festzustellen, dass eine entschädigungspflichtige Nichteinzonung vorliege. Dementsprechend sei die Einwohnergemeinde der Stadt Zug zu verpflichten, sie mit Fr. 15'440'100.-- für das enteignete Grundstück und Fr. 157'700.70 für nutzlos aufgewandte Planungskosten zu entschädigen; die Entschädigungen seien ab dem 1. Februar 1998 zu verzinsen. Zudem sei ihnen eine angemessene Entschädigung für das Verfahren vor Verwaltungsgericht zuzusprechen. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen, damit diese über die Höhe der Entschädigungen und die Nebenfolgen entscheide.
E. Der Stadtrat von Zug schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei.
Das Bundesamt für Raumentwicklung (ARE) hat auf eine Vernehmlassung verzichtet.
In ihrer Replik halten die Beschwerdeführer an ihren Anträgen und Begründungen fest.

Erwägungen:
1. Gegen den angefochtenen, kantonal letztinstanzlichen Endentscheid steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen und unterlagen vor Verwaltungsgericht mit ihrem Antrag auf Entschädigung wegen materieller Enteignung. Insofern sind sie zur Beschwerde legitimiert (<ref-law>). Da alle übrigen Sachurteilsvoraussetzungen vorliegen, ist auf die Beschwerde einzutreten.
Mit Beschwerde ans Bundesgericht kann insbesondere die Verletzung von Bundesrecht - einschliesslich Überschreitung oder Missbrauch des Ermessens - gerügt werden (<ref-law>). Das Bundesgericht wendet das Bundesrecht (mit Ausnahme der Grundrechte) von Amtes wegen an (<ref-law>). Es ist daher nicht an die Begründung der Parteien gebunden, sondern kann die Beschwerde auch aus andern als den geltend gemachten Gründen gutheissen oder den Entscheid mit einer Begründung bestätigen, die von jener der Vorinstanz abweicht (<ref-ruling> E. 1.4.1 S. 254 mit Hinweis).
Das Bundesgericht ist an den von der Vorinstanz festgestellten Sachverhalt gebunden, soweit dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. Alle Beteiligten gehen inzwischen davon aus, dass die Zuweisung der Parzelle 1643 zur Landwirtschaftszone im Zonenplan 1995 rechtlich als Nichteinzonung und nicht als Auszonung zu qualifizieren ist, weil die Nutzungsplanung 1982 der Stadt Zug materiell nicht den Grundsätzen des RPG entsprach. Mit der Revision von 1994 wurde somit erstmals eine RPG-konforme Nutzungsordnung geschaffen.
Die Parzelle 1643 liegt nicht im weitgehend überbauten Gebiet. Sie ist vielmehr Teil eines unüberbauten, landwirtschaftlich und gärtnerisch genutzten Grüngürtels, der die Stadt Zug vom Ortsteil Oberwil trennt und im Westen durch die SBB-Linie Zug-Arth-Goldau begrenzt wird.
Das rund 20'000 m2 grosse Grundstück wurde vom generellen Kanalisationsprojekt (GKP) der Stadt Zug vom 24. Mai 1972, revidiert im Februar 1984, erfasst. Dieses gelangte tatsächlich zur Anwendung, obwohl es - mangels kantonaler Genehmigung - nie rechtsgültig erlassen worden war. Ansonsten ist die Parzelle nicht erschlossen; insbesondere fehlt es an einem Anschluss an das öffentliche Strassennetz.
3. Die Beschwerdeführer sind der Auffassung, sie hätten damit rechnen dürfen, die Parzelle aus eigener Kraft erschliessen zu können, und hätten dafür ab dem Kauf am 26. November 1987 bis zum Erlass der Planungszone am 24. September 1990 bereits erhebliche Kosten aufgewendet. Ihres Erachtens sei zudem durch spezifische Handlungen der Behörden ein Vertrauenstatbestand geschaffen worden. Unter diesen Umständen sei eine materielle Enteignung zu bejahen.
3.1 Diese Auffassung wurde von der Schätzungskommission geteilt.
Sie nahm an, dass die Gesuchsteller in der Lage gewesen wären, das Grundstück 1643 separat, von unten her, d.h. durch Unterquerung der Bahnlinie, durch eine Quartierstrasse zu erschliessen, ohne dass hierfür ein Baulinien- oder Strassenplan erforderlich gewesen wäre. Zwar liege diesbezüglich keine eigentliche Zusicherung vor, jedoch habe sich die Stadt während zwei Jahren an der Erschliessungsplanung der Beschwerdeführer beteiligt und dabei z.T. die Federführung übernommen, ohne je einen Baulinien- oder Strassenplan zu verlangen. Zudem habe der Grosse Gemeinderat (als für den Erlass von Baulinienplänen zuständiges Organ) den Stadtrat im März 1990 ausdrücklich aufgefordert, eine rasche Erschliessungsplanung für das Gebiet Gimenen von unten her an die Hand zu nehmen.
Die Beschwerdeführer hätten bis Mitte 1991 Erschliessungs- bzw. Planungskosten in nicht unerheblichem Ausmass getätigt. Dabei anerkannte die Schätzungskommission Fr. 157'700.70 der von den Beschwerdeführern geltend gemachten Kosten (in Höhe von Fr. 227'000.--) als direkt mit der Erschliessung zusammenhängend.
Die Schätzungskommission hielt fest, dass die Beschwerdeführer die Parzelle am 26. November 1987 zum Preis von Fr. 9'116'740.-- (ca. Fr. 460/m2) erworben hätten. Damals sei die Bauordnung und der - formell RPG-konform erlassene - Zonenplan 1982 erst 5 Jahre in Kraft gewesen. Zwar habe der kantonale Richtplan 1987 eine Überprüfung der Zonierung verlangt; das kurz nach Erlass des Richtplans vom Kanton Zug im Einvernehmen mit der Stadt Zug abgegebene Kaufangebot für verschiedene Parzellen im Gebiet Gimenen (darunter auch Nr. 1643) für Fr. 50 Mio. habe jedoch auf deren weiteren Verbleib in der Bauzone basiert. Eine Mitteilung von Auszonungsabsichten sei - anders als gegenüber den Eigentümern der Grundstücke 1644 und 1645 - nicht erfolgt. Auch in den Entwürfen vom 22. Juni 1989 zum Teilrichtplan "Siedlung und Landschaft" sei die Parzelle der Beschwerdeführer noch als Wohngebiet bezeichnet worden, und der Teilrichtplan "Verkehr" vom gleichen Datum habe zur Erschliessung des Gebiets eine Sammelstrasse vorgesehen.
Die Beschwerdeführer hätten sofort nach dem Kauf der Liegenschaft Kontakt mit der Stadt aufgenommen und, für alle erkennbar, die Erschliessung mit erheblichem Kosteneinsatz vorangetrieben. Zur Bewilligung eines Erschliessungsprojekts - und damit auch für den Verzicht auf einen Baulinien- bzw. Strassenplan - sei der Stadtrat und nicht der Grosse Gemeinderat zuständig gewesen. Insofern bilde das rund zweijährige Zusammenwirken der Stadt mit den Beschwerdeführern durchaus ein im Sinne des Vertrauensprinzips relevantes Verhalten.
Durch die Erheblicherklärung der Motion Hausheer am 13. März 1990 und deren Bestätigung am 29. Mai 1990 habe sich zudem auch der Grosse Gemeinderat als eigentliches Planungsorgan hinter den weiteren Verbleib des Grundstücks 1643 in der Bauzone gestellt, was einer eigentlichen Zusicherung gleichgekommen sei. Noch im Beschluss des Stadtrates vom 13. Dezember 1990 zum Bericht Stadtplanung 1990 sei das Gebiet Tellenmatt als verkehrsberuhigte Zone Wohnen mitsamt einer Erschliessung von unten her bezeichnet worden, auch wenn die endgültigen Zonengrenzen noch nicht festgestanden hätten. Erst im Entwurf des Zonenplans vom Juli 1991 seien wesentliche Teile des Gebietes Gimenen zur Umzonung in die Landwirtschaftszone vorgesehen gewesen, und habe die Stadt jegliche weitere Mitwirkung an der Erschliessung des Grundstücks 1643 verweigert.
Gesamthaft kam die Mehrheit der Schätzungskommission daher zum Ergebnis, dass die Stadt Zug mit ihrem Verhalten gegenüber den Beschwerdeführern einen eigentlichen Vertrauenstatbestand gesetzt habe. Eine Minderheit der Schätzungskommission vertrat demgegenüber die Auffassung, dass aufgrund der Aussagen des Richtplans 1987 allen Grundeigentümern und Käufern der fraglichen Parzellen im Gebiet Tellenbach/Bröchli/Gimenen klar gewesen sein musste, dass im Rahmen der anstehenden Totalrevision der Nutzungsplanung zumindest ein wesentlicher Teil der dortigen Flächen nicht mehr dem Siedlungsgebiet zugewiesen würden. Vor diesem Hintergrund habe kein Vertrauen auf eine Einzonung entstehen können.
3.2 Das Verwaltungsgericht verneinte eine materielle Enteignung. Es ging davon aus, dass die strassenmässige Erschliessung der Parzelle weder rechtlich noch technisch für die nahe Zukunft gesichert gewesen sei und von den Beschwerdeführern nicht aus eigener Kraft hätte realisiert werden können. Es verneinte auch das Vorliegen erheblicher Erschliessungskosten und eines schutzwürdigen Vertrauenstatbestands.
Das Verwaltungsgericht hielt fest, dass die fehlende Groberschliessung des Gebiets nicht auf ein Versäumnis der Gemeinde zurückzuführen sei. 1990 sei der Planungshorizont von 15 Jahren bei Weitem noch nicht abgelaufen gewesen; ohnehin habe sich die Bevölkerung nicht entsprechend der seinerzeitigen Bedarfsprognose entwickelt. Insofern sei die Stadt nicht verpflichtet gewesen, das effektiv noch nicht benötigte Bauland zu erschliessen.
Für die Groberschliessung des Gebiets wäre nach Auffassung des Verwaltungsgerichts eine Gemeindestrasse erforderlich gewesen. Dies gelte nicht nur für die Erschliessung des gesamten Gimenengebiets, sondern auch für eine separate Erschliessung der Parzelle Nr. 1643 als bedeutenden Teil der Geländekammer. Deren Erschliessung hätte eine präjudizierende Wirkung für das gesamte Gebiet gehabt und hätte daher nicht einfach als Quartierstrasse oder gar als blosse Zufahrt realisiert werden können. Vielmehr wäre eine Sammelstrasse, d.h. eine Gemeindestrasse, erforderlich gewesen, die nur gestützt auf rechtskräftige Strassenbaulinienpläne hätte bewilligt werden dürfen. Hierfür hätte es der Zustimmung des Grossen Gemeinderats und - soweit ein Anschluss an die Artherstrasse als Kantonsstrasse nötig war - des Regierungsrats bedurft.
Seitens der Gesuchsteller hätten in den Jahren 1988 bis 1990 Abklärungen und Bemühungen zur separaten Erschliessung ihres Grundstücks durch eine Unterführung unter die SBB-Linie stattgefunden. Hierfür hätten Besprechungen mit Mitgliedern des Stadtrates und Chefbeamten der Stadt sowie Verhandlungen mit den SBB stattgefunden. Die hierfür nötigen Vorstudien seien von der Stadt, im Sinne einer Dienstleistung, unterstützt worden; diese habe aber nie die Federführung übernommen. Der Stadt sei es stets um die Erschliessung des gesamten Gimenengebiets gegangen, d.h. auch eine separate Privaterschliessung der Parzelle der Beschwerdeführer habe immer unter dem Vorbehalt einer gesamthaften politischen Beurteilung der Geländekammer gestanden.
Die von den Gesuchstellern geplante Privaterschliessung habe weder dem (ohnehin nur generellen) Strassenplan 1961 "Überbauung Friedbach und Gimenen" noch dem Verkehrsrichtplan vom 13. Oktober 1981 entsprochen. Dieser habe eine Groberschliessung des Gebiets Gimenen von oben her, via die Zugerbergstrasse, vorgesehen, in Form einer spangenförmigen Sammelstrasse, die den Verkehr bei St. Karl der Artherstrasse zuführen sollte. Die Vorlage für den Neubau der Gimenenstrasse mit der Bruibachbrücke sei jedoch dreimal (erstmals 1974 und letztmals am 26. November 1989) von den Stimmbürgern abgelehnt worden.
Neben dem - vom Grossen Gemeinderat zu bewilligenden - Baulinien- und Strassenplan wäre zudem ein eisenbahnrechtliches Plangenehmigungsverfahren erforderlich gewesen. Dieses sei von den Beschwerdeführern erst am 22. Mai 1991 (d.h. nach Erlass der Planungszone) eingeleitet worden. Nach der - zu erwartenden - Opposition durch private Einsprecher und den Stadtrat Zug hätten die Beschwerdeführer das Gesuch im Mai 1992 zurückgezogen.
Auch technisch wäre die von den Gesuchstellern bevorzugte Erschliessung zwar möglich, aber sehr schwierig und teuer gewesen.
Bei den durch die Schätzungskommission anerkannten Erschliessungskosten in Höhe von Fr. 157'700.70 handle es sich im Wesentlichen um Projektierungskosten, nicht zuletzt auch um Aufwand für (Rechts-)Beraterhonorare, und nicht um baulich in Erscheinung tretende, getätigte Erschliessungskosten. Die Aufwendungen seien mit Fr. 8.-/m2 bzw. 1.7 % des Erwerbspreises auch nicht erheblich, wenn man sie auf die Fläche (19'795 m2) bzw. auf den Kaufpreis (Fr. 9'116'740.--) umrechne.
Das Verwaltungsgericht betonte, dass das ganze Gebiet Tellenmatt/Bröchli/Gimenen, einschliesslich der Parzelle 1643, bereits im kantonalen Richtplan vom 1. September 1987 als "Gebiet mit zu prüfender Nutzung: Prüfung der Aus- oder Umzonung" bezeichnet worden sei. Gemäss Ziff. 13.0 des Richtplantextes mussten die Gemeinden die Nutzungsabsichten in diesen Gebieten überprüfen und im überarbeiteten Zonenplan gegebenenfalls neu festsetzen, wobei die "Zuordnung zu einer Bauzone eher die Ausnahme bleiben" sollte. Im Detailverzeichnis F41 des Berichts zur kantonalen Richtplanung 1987 sei zum Gebiet Bröchli/Gimenen (GPNU 01.05) im Sinne eines Zwischenergebnisses die Bemerkung "Siedlungstrennung" und als Idee für die damaligen SPV- und Bauzonen "Landwirtschaftsgebiet" angemerkt worden. Wichtig sei in diesem Zusammenhang, dass das umstrittene Grundstück Nr. 1643 in der Tellenmatt von den Behörden (gemäss Geodatenportal Zugis) ebenfalls unter der Gebietsbezeichnung "Bröchli" erfasst worden sei.
Die Stimmbürger hätten den (für die vorgesehene Erschliessung des Gebiets) erforderlichen Bau einer Bruibachbrücke am 26. November 1989 bereits zum dritten Mal (nach 1974 und 1977) abgelehnt. Am 2. November 1989 sei die "Volksinitiative zum Schutz unserer Grünflächen vor Zersiedlung" eingereicht worden, die in der Volksabstimmung vom 24. Juni 1990 mit mehr als 60% Ja-Stimmen angenommen worden sei. Die Initiative habe sich insbesondere gegen die Überbauung des Gebiets Gimenen/Bröchli gerichtet. Daraufhin habe der Regierungsrat für das ganze Gebiet Gimenen/Bröchli/Tellenmatt eine Planungszone erlassen.
Bereits am 12. April 1989 habe der Stadtrat von Zug das Leitbild 89 beschlossen, von dem der Grosse Gemeinderat mit Beschluss vom 9. Januar 1990 zustimmend Kenntnis genommen habe. Dort sei festgehalten worden, dass der unüberbaute Teil der Gimenen eine wohltuende Grünzäsur zwischen Zug und Oberwil bilde. Die Erschliessung des oberen Teils sei über die Gimenen-Brücke vorgesehen; diejenige des unteren Teils sei noch offen. Mit der kommenden Zonenplanrevision solle bestimmt werden, ob dieses Gebiet in dieser Generation überbaut oder aber der kommenden Generation als Reserve offengehalten werden solle. Die guten Wohnlagen längs der SBB-Linie seien wegen der projektierten Begradigung der SBB-Geleise planerisch blockiert. Als Ziel wurde formuliert: "Der grössere, noch unüberbaute Teil der Gimenen, der auch kaum sinnvoll von oben erschlossen werden kann und dessen Erschliessung von unten durch die Projekte der SBB erschwert ist, soll als Baulandreserve für die nächste Generation offengehalten werden."
Das Verwaltungsgericht erwog, dass es ohne Weiteres Sinn gemacht habe, das ganze Gebiet Gimenen (einschl. der Parzelle 1643) im kantonalen Richtplan, im städtischen Leitbild 89 und schliesslich im Zonenplan 1992 als Landwirtschaftszone zu erfassen, bilde es doch insgesamt eine grosse Geländekammer am unteren Hang des Zugerbergs, im Westen begrenzt durch die SBB-Linie. Es bilde einen breiten Trenngürtel zwischen den Siedlungsgebieten der Stadt Zug und Oberwils. Die Trennung sei optisch markant erlebbar und werde durch die durchgehende landwirtschaftlich-gärtnerische Nutzung hervorgehoben. Zudem hätten die Beschwerdeführer gewusst, dass hier seit dem Erlass des Zonenplans 1982 kein Neubau mehr errichtet worden sei. Der Kauf der Parzelle sei erst nach Erlass des Richtplans erfolgt, aufgrund dessen die Beschwerdeführer die zukünftige Zuweisung ihrer Parzelle zum Landwirtschaftsgebiet zumindest in Betracht ziehen mussten.
Weder vom Stadtrat noch vom Grossen Gemeinderat seien mündliche oder schriftliche Zusicherungen abgegeben worden. Auch aus den verschiedenen politischen Motionen und Voten im Parlament lasse sich kein Vertrauenstatbestand ableiten. Zwar sei klar gewesen, dass die Mehrheit des Grossen Gemeinderats die Verwirklichung der städtischen Bauvorhaben in der Gimenen möglichst fördern wollte und der Stadtrat daher beauftragt wurde, eine Erschliessung "von unten her" zu prüfen. Konkrete Zusicherungen zur Erschliessung der unten liegenden privaten Grundstücke bzw. ihrer Zonierung seien jedoch nicht gemacht worden. Die Beschwerdeführer hätten somit nur (aber immerhin) hoffen und darauf spekulieren können, dass ihre "Erschliessungsideen" zu ihren Gunsten in die Erschliessungsbemühungen und Zonierungsabsichten der Stadt einfliessen könnten.
Nichts anderes gelte für das Kaufangebot des Kantons an die Y._ AG vom 21. September 1987. Zwar hätten die übrigen Mitbieter aufgrund des Kaufpreisangebots (das weit über den damaligen Landwirtschaftspreisen lag) davon ausgehen dürfen, dass eine Umzonung in die Landwirtschaftszone nicht unmittelbar bevorstand. Immerhin aber habe der Kanton ausdrücklich auf die Möglichkeit der Änderung der planungsrechtlichen Situation hingewiesen. Es habe sich insofern um ein spekulatives Geschäft gehandelt, das realistischerweise von Anfang an mit Unsicherheiten und blossen Realisierungshoffnungen verbunden gewesen sei.
Das Verwaltungsgericht verneinte deshalb sowohl einen Entschädigungsanspruch aus materieller Enteignung als auch einen Anspruch der Beschwerdeführer auf Ersatz nutzlos gewordener Planungskosten.
3.3 Die Beschwerdeführer räumen ein, dass die von der Vorinstanz verlangte gebietsweise und nicht parzellenbezogene Erschliessung den Planungsgrundsätzen des RPG entspreche. Das Verwaltungsgericht habe jedoch seine Funktion im vorliegenden Verfahren verkannt: Es sei nicht darum gegangen, eine konkrete Erschliessung zu überprüfen, sondern darum, behördliches Verhalten und das dadurch bei den bauwilligen Beschwerdeführern bewirkte Vertrauen zu beurteilen. Zu prüfen sei deshalb nicht, ob die Praxis der Behörden den bundesrechtlichen Anforderungen entsprochen habe, sondern wie sie damals nach aussen in Erscheinung getreten sei und welche Schlüsse die Beschwerdeführer aus dem Ablauf der Ereignisse hätten ziehen dürfen.
Die Beschwerdeführer betonen, dass für die Bewilligung der Erschliessung und der anschliessenden Überbauung der Parzelle 1643 der Baupräsident bzw. das Bauamt zuständig gewesen sei. Diese hätten die Erschliessungsideen der Beschwerdeführer nicht passiv entgegengenommen, sondern aktiv an der Erschliessungsplanung mitgewirkt. Die Kontakte zu den Baubehörden seien enger gewesen, als vom Verwaltungsgericht dargestellt: Aktenkundig seien drei Sitzungen mit Stadträten und Chefbeamten (am 7. März 1988, 31. März 1988 und 8. März 1990) sowie zwei Sitzungen in kleinerer Besetzung (am 14. November 1988 und im Februar 1990).
In einer ersten Phase sei es um die separate Erschliessung der Parzelle gegangen. Hierfür sei im April 1989 ein Bauermittlungsgesuch eingereicht worden, mit drei Erschliessungskonzepten: eine Teilüberbauung mit provisorischer Zufahrt über den Bröchliweg (Plan 1), eine Vollüberbauung mit Bahnunterführung ab der Tellenmattstrasse (Plan 2) und eine Vollüberbauung nach "Streckung" der SBB-Linie (Plan 3; im Zuger Richtplan war damals die Streckung der Eisenbahnlinie mit Tunnelierung oberhalb der Parzelle 1643 vorgesehen.). Noch im Februar 1990 sei mit dem Chef Kanalisation der Stadt der Anschlusspunkt an die Kanalisation festgelegt worden. Die Stadt habe die Beschwerdeführer damit zumindest konkludent im Glauben bestärkt, ihre Bauermittlung sei auf gutem Weg und es sei vernünftig, erhebliche Mittel in die weitere Planung der Erschliessung und der Baueingabe zu investieren.
Die Baubehörden hätten sogar eine provisorische Erschliessung für zwei Landhäuser auf GS 1643 ab dem bestehenden Bröchliweg als möglich und zulässig erachtet. Hätten die Beschwerdeführer dieses Vorgehen gewählt, hätten sie mit dem Segen der Bauverwaltung ein fait accompli für die Überbaubarkeit der ganzen eingezonten Parzelle geschaffen, da es sinnlos und ein Musterbeispiel für Streubauweise gewesen wäre, die weitere Überbauung zu stoppen. Das so bekundete "grüne Licht" für die Überbaubarkeit habe die Beschwerdeführer in ihrem Vertrauen so sehr bestärkt, dass sie gleich die definitive Erschliessungsplanung für die ganze Parzelle an die Hand genommen hätten.
Auch in der zweiten Phase, nach der gescheiterten Abstimmung über die Bruibachbrücke, habe die Stadt die Erschliessungsplanung der Beschwerdeführer unterstützt. Dem Stadtrat wäre es damals sehr recht gewesen, wenn die Beschwerdeführer den "gordischen Knoten" der SBB-Unterquerung mit einer später für eine Gemeindestrasse tauglichen Lösung durchhauen hätten. Die Stadt habe deshalb neu den Nachweis verlangt, dass auch die übrigen Grundstücke am Gimenenhang über die Parzelle 1643 erschlossen werden könnten. Der Baupräsident habe in der Sitzung vom 8. März 1990 eine erheblich grössere Dimensionierung der Strasse mit wesentlich grösserem konstruktivem und finanziellem Aufwand verlangt. Damit sei bei den Beschwerdeführern Vertrauen in die Kontinuität des Planungsprozesses geweckt worden und sie seien zur Übernahme weiterer, finanziell erheblicher Verpflichtungen veranlasst worden.
Das Verwaltungsgericht wecke in willkürlicher Weise den Eindruck, die Baueingabe vom 22. Juni 1990 sei nicht ernsthaft gewesen bzw. sei nur im Hinblick auf ein Entschädigungsverfahren erfolgt. Der im Juni 1990 eingereichte Plansatz habe auf einer von der Firma Wild-Leitz durchgeführten digitalen Vermessung des Geländes beruht und belege, dass die Erschliessungsplanung weit über das Entwurfsstadium hinaus gediehen war. Aufgrund der Annahme der Grünflächeninitiative zwei Tage nach Einreichung des Gesuchs und der kurz darauf verhängten Planungszone sei das Vorhaben blockiert gewesen. Es könne den Beschwerdeführern daher kein Vorwurf gemacht werden, dass sie unter diesen Umständen nicht auf der Behandlung ihres Baugesuchs bestanden hätten.
Die Beschwerdeführer weisen darauf hin, dass sich die SBB im Entwurf einer Grundsatzvereinbarung vom 13. Juli 1989 noch selbst als Baubewilligungsbehörde für die geplante Unterführung bezeichnet habe (anders als in der definitiven Vereinbarung von Juli/August 1990, wo das BAV als Bewilligungsbehörde genannt wurde). Die Beschwerdeführer hätten deshalb mit der Erteilung der Plangenehmigung rechnen dürfen. Da es damals nur um die Erschliessung der Parzelle Nr. 1643 durch eine kleiner dimensionierte Unterführung gegangen sei, seien auch keine Einsprachen zu erwarten gewesen (anders als beim 1991 angehobenen Plangenehmigungsverfahren, das die Erschliessung des gesamten Gimenen-Gebiets betroffen habe).
Das Leitbild 89 der Stadt Zug vom 12. April 1989 sei nicht grundeigentümerverbindlich gewesen und habe daher die Überbaubarkeit der Parzelle 1643 nicht verhindert. Damals sei man von der RPG-Konformität der erst fünf Jahre zuvor erlassenen Zonierung ausgegangen. Erst der Bundesgerichtsentscheid i.S. Cham vom 22. Mai 2000 (1A.155/1999) habe diese Überzeugung in Frage gestellt. Das Gebiet Tellenmatt oberhalb der Eisenbahnlinie sei noch im Bericht des Stadtrates zur Stadtplanung und im Teilrichtplan Siedlung und Landschaft, 2. Vorprüfung, beide vom 13. Dezember 1990, als Wohnzone vorgesehen gewesen. Auch der Regierungsrat sei bei seinem Kaufangebot 1987 von der Überbaubarkeit der Wohnzonen ausgegangen; der Hinweis auf hängige Auszonungsbegehren habe sich offensichtlich auf die SPV-Zonen am Gimenenhang bezogen.
Die Beschwerdeführer erachten die vom Verwaltungsgericht vorgenommene Umrechnung der Erschliessungskosten auf die Landfläche bzw. auf den Kaufpreis als nicht sachgerecht. Zu beurteilen sei, was ein Enteigneter zufolge nachfolgend enttäuschten Vertrauens in einen mit den Behörden unternommenen Planungsprozess investiert habe. Dabei seien Aufwendungen von Fr. 157'700.-- für sich allein schon erheblich. Setze man die Summe in Relation zu den Kosten eines allein für die Groberschliessung der Parzelle 1643 konzipierten "kleinen" Erschliessungsbauwerks, ergebe sich ein Anteil von 10 %, der ebenfalls erheblich sei.
Aus allen diesen Gründen hätten die Beschwerdeführer bis zum Erlass der Planungszone im September 1990 darauf vertrauen dürfen, ihre Parzelle aus eigener Kraft erschliessen und überbauen zu können und hätten hierfür erhebliche Kosten aufgewendet.
3.4 Die Stadt Zug macht dagegen geltend, im Zeitpunkt des Erlasses der Planungszonen hätten die Beschwerdeführer die "kleine" Erschliessungsvariante schon aufgegeben gehabt. Allein für die Strassenerschliessung unter der Eisenbahnlinie hindurch hätte nach Auskunft der Karl Steiner AG mit Kosten von rund Fr. 6.5 Mio. gerechnet werden müssen. Gemessen daran seien die bereits aufgewendeten Kosten für die Erschliessungsplanung sehr bescheiden.
Die Stadt bestreitet, dass die Erschliessung der Parzelle 1643 in enger Zusammenarbeit mit dem Baupräsidenten und dem Bauamt der Stadt Zug vorangetrieben worden sei. Bei den Besprechungen mit den Beschwerdeführern habe es sich nur um einen - auch heute noch gebräuchlichen - Meinungsaustausch zwischen Behördenvertretern und bauwilligen Privaten gehandelt. Der für die städtische Erschliessungsplanung zuständige Stadtingenieur habe nach Angaben des Mitarbeiters der Karl Steiner AG nie an die Realisierbarkeit der Erschliessungslösungen der Beschwerdeführer geglaubt und habe daher grosse Zurückhaltung gegenüber deren Projekten geübt.
In der ersten Phase hätten sich die Erschliessungsvorstellungen der Beschwerdeführer ("von unten") und diejenigen der Stadt ("von oben") diametral entgegengestanden. In der zweiten Phase, spätestens mit der Verbindlicherklärung der Motion Hausheer am 13. März 1990, sei eine private Erschliessungsplanung im Gebiet Gimenen ohnehin ausgeschlossen gewesen, weil der Grosse Gemeinderat den Stadtrat beauftragt hatte, eine Vorlage für die Erschliessung der Gimenen "von unten" her zu erarbeiten.
Die Baueingabe vom 22. Juni 1990 sei bei Weitem noch nicht ausführungs- und bewilligungsreif gewesen, sondern habe sich etwa auf Stufe Vorstudie befunden. Weder seien geologische Bodenuntersuchungen noch ausreichende Berechnungen durchgeführt worden, noch habe es irgendeine Detailplanung oder eine verlässliche Kostenschätzung gegeben. Zudem sei das Baugesuchsformular nicht ausgefüllt gewesen. Vermutlich hätten die Beschwerdeführer damals die noch unfertigen Planentwürfe eingereicht, um das Projekt noch vor der Abstimmung über die Grünflächeninitiative bei den städtischen Planungs- und Baubehörden zu deponieren. In dem - für die Erteilung von Baubewilligungen zuständigen - Stadtrat sei die von den Beschwerdeführern verfolgte Privaterschliessung nie ein Thema gewesen.
Schon im (immerhin behördenverbindlichen) Leitbild 1989 habe sich der Stadtrat gegen die Einzonung des streitigen Gebiets ausgesprochen. Erst auf Drängen der Beschwerdeführer habe er sich vorübergehend dazu bewegen lassen, eine Einzonung von GS 1643 in Erwägung zu ziehen. Im zweiten Bericht des Stadtrates zur Stadtplanung vom 8. Juli 1991 und erst recht in der Stadtplanungsvorlage vom 14. April 1992 an den Grossen Gemeinderat sei die Einzonung der Parzelle bereits wieder kein Thema gewesen.
4. Vorab sind die formellen Rügen der Beschwerdeführer sowie ihre Sachverhalts- bzw. Willkürrügen zu behandeln. Anschliessend ist zu prüfen, ob die vorliegend streitige Nichteinzonung eine entschädigungspflichtige materielle Enteignung darstellt (E. 5).
4.1 Die Beschwerdeführer werfen dem Verwaltungsgericht eine Verletzung des rechtlichen Gehörs vor, weil es entscheidwesentliche Fakten willkürlich verschwiegen habe. Im Einzelnen kann hierfür auf die Beschwerdeschrift (Rz. 15, 20f., 29 und 31) verwiesen werden.
Das Verwaltungsgericht hat sich jedoch in seinem über hundertseitigen Urteil ausführlich mit den Argumenten und den eingereichten Unterlagen der Beschwerdeführer befasst, hat daraus allerdings andere Schlüsse gezogen als diese. Hierfür kann insbesondere auf die Erwägungen 6c S. 50 f. des angefochtenen Entscheids (betr. die Sitzung mit Vertretern der Finanzabteilung und des Bauamts vom 7. März 1988 zur "Erschliessung Gimenen im Bereich Bröchli"), E. 6d S. 51 ff. (zu vom Bauamt 1988 erstellten Planunterlagen zu Erschliessungsvarianten Oberwil-Gimenen), E. 11 h S. 96 (zur tatsächlichen Bewilligungspraxis der Stadt betr. Privaterschliessungen Ende der 80er und Anfang der 90er Jahre), E. 6a S. 48 (zur Vereinbarkeit der Erschliessungspläne der Beschwerdeführer mit dem Verkehrsrichtplan der Stadt vom 13. Oktober 1981) und E. 6j S. 63 f. (zur Besprechung mit dem Bauamt vom 8. März 1990 mit Vorgaben zur Dimensionierung der Strasse) verwiesen werden. Die wenigen, im Urteil nicht erwähnten Vorbringen der Beschwerdeführer (insbes. Besprechung mit dem Chef Kanalisation im Februar 1990) erachtete das Verwaltungsgericht offensichtlich nicht als entscheidrelevant.
Eine Verletzung des rechtlichen Gehörs ist daher zu verneinen.
4.2 Die Beschwerdeführer rügen sinngemäss eine offensichtlich falsche Sachverhaltsfeststellung bzw. eine willkürliche Rechtsanwendung, soweit das Verwaltungsgericht auch für Quartierstrassen einen Baulinien- bzw. Strassenplan für erforderlich gehalten habe: Nach dem damals geltenden Baugesetz für den Kanton Zug vom 18. Mai 1967 (aBauG) seien solche Pläne nur für Gemeindestrassen, nicht aber für Quartierstrassen obligatorisch gewesen (§ 40 i.V.m. § 34 aBauG in fine).
Die Vorinstanz ging jedoch davon aus, dass die Erschliessung der Parzelle 1643 mit derjenigen des gesamten Gimenengebiets hätte koordiniert werden müssen und deshalb auch für eine Separaterschliessung der Parzelle 1643 eine Gemeindestrasse erforderlich gewesen wäre (vgl. insbes. E. 5d S. 41 f. des angefochtenen Entscheids und dazu unten E. 5.1 - 5.3). Es ist unstreitig, dass jedenfalls eine Gemeindestrasse nur aufgrund eines Baulinien- bzw. Strassenplans hätte bewilligt werden können, für den der Grosse Gemeinderat zuständig gewesen wäre. Insofern ist die von den Beschwerdeführern aufgeworfene Rechtsfrage nicht entscheiderheblich.
4.3 Soweit die Beschwerdeführer rügen, das Bauamt und nicht der Stadtrat von Zug sei für die Bewilligung privater Erschliessungen zuständig gewesen, belegen sie nicht, weshalb die Rechtsauffassung des Verwaltungsgerichts (die von der Stadt Zug geteilt wird) willkürlich sei (<ref-law>). Im Übrigen räumen sie in ihrer Replik (Rz. 26) selbst ein, dass formell der Stadtrat für die Bewilligung zuständig gewesen wäre, wenn auch materiell der Entscheid beim Bauamt gelegen hätte.
5. Nichteinzonungen lösen nach der bundesgerichtlichen Rechtsprechung grundsätzlich keine Entschädigungspflicht aus. Sie treffen den Eigentümer nur ausnahmsweise enteignungsähnlich, so etwa dann, wenn er überbaubares oder grob erschlossenes Land besitzt und für die Erschliessung und Überbauung seines Landes schon erhebliche Kosten aufgewendet hat, wobei diese Voraussetzungen in der Regel kumulativ erfüllt sein müssen. Sodann können weitere besondere Gesichtspunkte des Vertrauensschutzes so gewichtig sein, dass ein Grundstück unter Umständen hätte eingezont werden müssen. Ein Einzonungsgebot kann ferner zu bejahen sein, wenn sich das fragliche Grundstück im weitgehend überbauten Gebiet befindet. Erforderlich ist jeweils eine Gesamtwürdigung der rechtlichen und tatsächlichen Gegebenheiten (vgl. zum Ganzen <ref-ruling> E. 2.2 und 2.3 S. 220 ff. mit Hinweisen).
Massgeblicher Stichtag für diese Beurteilung ist grundsätzlich das Inkrafttreten des neuen Zonenplans, der die Eigentumsbeschränkung bewirkt. Geht dem definitiven Eingriff jedoch eine provisorische Massnahme voraus, darf damit nicht zum Nachteil des Betroffenen ein Ausschluss der Entschädigungspflicht begründet werden (<ref-ruling> E. 2.4 S. 222 mit Hinweisen). Dies hat - wie die Vorinstanz und die Beschwerdeführer übereinstimmend annehmen - zur Folge, dass im vorliegenden Fall auf die Situation bei Erlass der Planungszone am 24. September 1990 abzustellen ist.
5.1 In diesem Zeitpunkt war die von der Stadt ursprünglich beabsichtigte Erschliessung des Gimenengebiets "von oben" (via Zugerbergstrasse und eine Brücke über den Bruibach) zum dritten Mal von den Stimmbürgern abgelehnt worden und damit faktisch gescheitert. Der Grosse Gemeinderat hatte den Stadtrat deshalb beauftragt, eine Erschliessung "von unten", mittels einer Eisenbahnunterführung, zu planen. In dieser Situation war klar, dass die (zuunterst liegende) Parzelle 1643 nicht separat durch eine Quartierstrasse erschlossen werden könnte, sondern eine Gemeindestrasse erforderlich war, mit der auch die weiter oben liegenden Bauzonen erschlossen werden könnten. Für die Bewilligung dieser Quartierstrasse wäre nicht nur eine eisenbahnrechtliche Plangenehmigung, sondern insbesondere auch ein Baulinien- bzw. Strassenplan erforderlich gewesen. Zu diesem Zeitpunkt konnten die Beschwerdeführer daher nicht mehr darauf vertrauen, ihre Parzelle aus eigener Kraft erschliessen zu können.
5.2 Fraglich ist dagegen, ob eine Separaterschliessung der Parzelle Nr. 1643 mittels einer Quartierstrasse in der ersten Phase (vor der dritten Abstimmung über die Bruibachbrücke) möglich gewesen wäre, als Ergänzung zu der damals von der Stadt angestrebten Groberschliessung des Gimenengebiets "von oben" her.
Das Verwaltungsgericht hat jedoch zutreffend dargelegt, dass die Groberschliessung der rund 20'000 m2 grossen Parzelle 1643 und die hierfür notwendigen Eisenbahn-Unterführung eine Koordination mit der Groberschliessung des übrigen Gimenengebiets vorausgesetzt hätte. Dies spricht für die Notwendigkeit eines vorgängigen Baulinien- bzw. Strassenplans. Zudem wäre ein eisenbahnrechtliches Plangenehmigungsverfahren notwendig gewesen. Auch wenn das ursprüngliche Projekt einer Bahnunterführung kleiner dimensioniert war als das 1991 eingereichte Plangenehmigungsgesuch, wäre mit Einsprachen zu rechnen gewesen, insbesondere wegen der präjudiziellen Wirkung des Projekts für die in der Bevölkerung umstrittene Überbauung des Gimenengebiets. Insofern kann nicht davon ausgegangen werden, dass es dem Bauamt (faktisch) freigestanden hätte, auf eine vorgängige Baulinien- und Strassenplanung zu verzichten, ohne dass dies in einem Rechtsmittelverfahren hätte überprüft werden können.
5.3 Etwas anderes gilt möglicherweise für eine Erschliessung der Parzelle für nur zwei Häuser ab dem Bröchliweg. Diese Lösung hätte keine Unterführung unter die SBB-Linie vorausgesetzt und hätte daher möglicherweise mit einer blossen Quartierstrasse, ohne vorgängigen Baulinien- bzw. Strassenplan, bewilligt werden können. Dagegen spricht allerdings die - auch von den Beschwerdeführern betonte - präjudizielle Wirkung des "ersten Spatenstichs" im Gimenengebiet.
Letztlich kann die Frage offenbleiben: Zum einen hatte das Bauamt diese Lösung lediglich als Provisorium vorgesehen, d.h. unter Vorbehalt des Nachweises einer definitiven Erschliessungslösung. Zum anderen wurde diese Minimallösung auch von den Beschwerdeführern nicht weiter verfolgt. Ihre Erschliessungsplanung und die hierfür gemachten Aufwendungen zielten vielmehr darauf ab, ihre Parzelle vollständig erschliessen und überbauen zu können.
5.4 Hinzu kommt, dass die Realisierungsmöglichkeit einer Erschliessung und Überbauung des Landes allein grundsätzlich nicht genügt, um eine materielle Enteignung durch Nichteinzonung zu begründen:
Nach der oben (E. 5) zitierten Rechtsprechung löst die Nichteinzonung von Land - selbst wenn dieses schon groberschlossen ist - nur ausnahmsweise einen Entschädigungsanspruch aus. Ausserhalb des weitgehend überbauten Gebiets wird i.d.R. verlangt, dass der Eigentümer bereits erhebliche Aufwendungen für die Erschliessung und/ oder Überbauung seines Landes getätigt hat. Dabei muss es sich um Investitionen handeln, die baulich in Erscheinung treten (<ref-ruling> nicht publ. E. 5.2; <ref-ruling> E. 5b S. 437; <ref-ruling> E. 5a S. 146 f., 112 Ib 396 E. 6c S. 402 f., vgl. auch Urteil 1A.216/1996 vom 4. April 1997 E. 5a, in: Pra 86/1997 Nr. 104 S. 569; Urteil 1A.264/1999 vom 7. Juli 2000 E. 4c/aa). Nutzlos gewordene Planungs- und Projektierungskosten, die sich nicht in einem Erschliessungsbauwerk niedergeschlagen haben, geben nach dieser Rechtsprechung grundsätzlich (von besonderen Gründen des Vertrauensschutzes abgesehen; vgl. dazu unten, E. 5.5) keinen Anspruch auf Entschädigung wegen materieller Enteignung. Dem Bauherrn steht lediglich unter besonderen Voraussetzungen ein Anspruch auf Aufwendungsersatz gegenüber dem Gemeinwesen zu (vgl. unten E. 5.5.4).
Bei den von den Beschwerdeführern geltend gemachten Kosten für die Erschliessung handelt es sich ausschliesslich um Planungs- und Projektierungskosten, die nie baulich in Erscheinung getreten sind: Die Parzelle 1643 ist bis heute nicht groberschlossen. Insofern kann offen bleiben, ob die Aufwendungen der Beschwerdeführer für sich allein oder in Relation zur Grundstücksfläche, zum Kaufpreis oder zu den projektierten Erschliessungskosten erheblich waren.
5.5 Näher zu prüfen ist, ob im vorliegenden Fall Gesichtspunkte des Vertrauensschutzes vorliegen, die so gewichtig sind, dass eine materielle Enteignung zu bejahen ist.
Wie das Verwaltungsgericht zutreffend dargelegt hat, gibt es gewisse Elemente, die für und andere, die gegen ein schutzwürdiges Vertrauen der Beschwerdeführer in die Einzonung ihrer Parzelle sprachen:
5.5.1 Für die Einzonung sprach vor allem der Umstand, dass die Parzelle 1643 seit der Erarbeitung der Stadtplanung Zugs in den 70er Jahren als zukünftiges Siedlungsgebiet vorgesehen war: Es lag gemäss dem vom Regierungsrat per 1. Juli 1975 erlassenen Ersatzzonenplan in der Wohnzone; 1982 wurde es im (vermeintlich RPG-konformen) Zonenplan der Gemeinde Zug wiederum der Wohnzone zugewiesen. Der Planungshorizont dieser Zonierung war im Jahr 1990 (bei Erlass der Planungszone) noch lange nicht abgelaufen. Die städtischen Behörden befürworteten eine Wohnüberbauung im Gimenengebiet und standen deshalb auch den Erschliessungsplänen der Beschwerdeführer zumindest wohlwollend gegenüber.
5.5.2 Gegen die Zuteilung der Parzelle zum Baugebiet sprach dagegen der kantonale Richtplan 1987, der die Gemeinde anhielt, am Gimenenhang die Aus- oder Umzonung zu prüfen. Dieser Auftrag bezog sich nicht nur auf die SPV-Zonen, sondern ausdrücklich auch auf die Bauzonen oberhalb der Bahnlinie. Ins Gewicht fiel zudem die Haltung der Stimmbürger, die seit den 70er Jahren alle Projekte zur Erschliessung des noch unüberbauten, landwirtschaftlich genutzten Gimenengebiets abgelehnt hatten und sich 1990 klar für die Annahme der Grünflächen-Initiative aussprachen. Insofern mussten die Beschwerdeführer beim Kauf der Parzelle im Herbst 1987 wie auch bei ihren späteren Erschliessungsbemühungen damit rechnen, dass die Parzelle bei der nächsten Zonenplanrevision der Landwirtschaftszone zugeteilt werden könnte.
5.5.3 Unter diesen Umständen ist dem Verwaltungsgericht zuzustimmen, dass dem Geschäft von Anfang an ein unsicherer, spekulativer Charakter anhaftete: Die Beschwerdeführer durften hoffen, aber nicht darauf vertrauen, dass ihre Parzelle im überarbeiteten Zonenplan der Bauzone zugeteilt werden würde. Insofern erfolgten die Aufwendungen für die Erschliessung der Parzelle auf eigenes Risiko. Sie verfolgten das Ziel, die öffentliche Einzonungsdiskussion zu beeinflussen bzw. die Erschliessung und Überbauung der Parzelle 1643 noch vor der Zonenplanrevision zu realisieren, um damit vollendete Tatsachen zu schaffen. Die Beschwerdeführer konnten im Übrigen hoffen, dass die (damals im Richtplan vorgesehene) "Streckung" der SBB-Linie realisiert werden würde, so dass die Bahnlinie neu oberhalb der Parzelle 1643 verlaufen wäre. Diese hätte dann mit den übrigen Grundstücken der Beschwerdeführer vereinigt und problemlos erschlossen werden können, mit der Folge, dass sie höchstwahrscheinlich auch eingezont worden wäre. Letztlich haben sich diese Hoffnungen jedoch nicht realisiert, mit der Folge, dass die Investitionen der Beschwerdeführer sich als nutzlos erwiesen haben. Dieses Risiko tragen sie und nicht die Stadt Zug.
5.5.4 Es ist auch nicht ersichtlich, dass die besonderen Voraussetzungen für den Ersatz von Planungs- und Projektierungskosten vorliegen (vgl. dazu <ref-ruling> E. 4a S. 237 mit Hinweis): Weder war die Einreichung des Baugesuchs der Beschwerdeführer Anlass zur Änderung der planungsrechtlichen Vorschriften, noch wurden ihnen nach dem oben Gesagten Zusicherungen auf den Fortbestand der geltenden Bauvorschriften gegeben.
5.6 Es mag unbefriedigend sein, in Fällen wie dem Vorliegenden nur die Alternative zu haben, den Eigentümern alles (hier: rund 15.5 Mio. Franken) oder nichts zuzusprechen. Dies ist jedoch die Konsequenz der aktuellen Rechtslage, die bei Vorliegen einer materiellen Enteignung einen Anspruch auf eine volle Entschädigung gewährt (<ref-law>) und keine Entschädigung für planungsbedingte Minderwerte unterhalb dieser Schwelle vorsieht.
6. Nach dem Gesagten ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig und haben keinen Anspruch auf eine Parteientschädigung (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 30'000.-- werden den Beschwerdeführern auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Einwohnergemeinde der Stadt Zug, dem Verwaltungsgericht des Kantons Zug, Verwaltungsrechtliche Kammer, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 16. Januar 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber