Sachverhalt:
A. Mit Eingabe vom 16. April 1992 stellten die im Rubrum aufgeführten Mitglieder der Erbengemeinschaft E X._ beim Verwaltungsgericht des Kantons Zug ein Gesuch um Feststellung einer materiellen Enteignung und einer Entschädigungspflicht. Das Gesuch betraf das der Erbengemeinschaft gehörende und auf dem Gebiet der Gemeinde Zug liegende Grundstück Nr. 768. Die Erbengemeinschaft machte geltend, die Zonenplanung der Einwohnergemeinde Zug aus dem Jahr 1981/82 habe eine materielle Enteignung bewirkt, indem ein Teil des Grundstücks der Zone des öffentlichen Interesses zugewiesen worden sei. Das Verwaltungsgericht überwies das Verfahren der Schätzungskommission des Kantons Zug, welche eine einstweilige Sistierung verfügte. Am 6. September 2006 erneuerten und präzisierten die Gesuchsteller ihre Eingabe.
Mit Beschluss vom 27. Oktober 2008 stellte die Schätzungskommission fest, dass die geltend gemachten Ansprüche insoweit verjährt seien, als sie die Fläche des Grundstücks Nr. 768 beträfen, die bereits mit der Ersatzbauordnung bzw. dem Ersatzzonenplan von 1975 der Zone des öffentlichen Interesses zugewiesen worden sei. Über Bestand und Höhe der geltend gemachten Ansprüche bezüglich der restlichen Fläche werde im weiteren Verfahren entschieden.
Gegen diesen Entscheid reichten die Mitglieder der Erbengemeinschaft Beschwerde beim Verwaltungsgericht ein. Sie beantragten, der Entscheid sei insoweit aufzuheben, als darin festgestellt werde, ein Teil des geltend gemachten Entschädigungsanspruchs sei verjährt. Zudem sei festzustellen, dass die Verjährung noch nicht eingetreten sei. Mit Urteil vom 30. November 2009 wies das Verwaltungsgericht das Rechtsmittel ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 11. Februar 2010 beantragen die Mitglieder der Erbengemeinschaft, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei festzustellen, dass die Verjährung des Entschädigungsanspruchs zufolge materieller Enteignung noch nicht eingetreten sei. Eventualiter sei festzustellen, dass der Fristenlauf der Verjährung der Entschädigungsforderung aus materieller Enteignung am 20. April 1982 (Inkrafttreten des Zonenplans und der Bauordnung der Stadt Zug) zu laufen begonnen hat. Subeventualiter sei festzustellen, dass der Fristenlauf der Verjährung vor dem 1. Juli 1985 unterbrochen wurde oder die Verjährungsfrist stillstand. Im Eventual- und Subeventualfall sei die Angelegenheit zur ergänzenden Ermittlung des Sachverhalts und/oder zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen.
Das Verwaltungsgericht des Kantons Zug beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Schätzungskommission des Kantons Zug und die Einwohnergemeinde Zug schliessen auf die Abweisung der Beschwerde. Das Bundesamt für Raumentwicklung hat auf eine Vernehmlassung verzichtet. In ihrer Stellungnahme dazu halten die Beschwerdeführer im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest.

Erwägungen:
1. 1.1 Der angefochtene, kantonal letztinstanzliche Entscheid verneint eine Entschädigungspflicht aus materieller Enteignung. Dabei geht es um eine öffentlich-rechtliche Angelegenheit im Sinne von <ref-law>. Ein Ausschlussgrund nach Art. 83 und 85 BGG liegt nicht vor. Am bundesgerichtlichen Verfahren beteiligen sich sämtliche Gesamteigentümer des Grundstücks Nr. 768. Sie haben allesamt auch am vorinstanzlichen Verfahren teilgenommen, sind durch den angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>).
Die Schätzungskommission traf eine Unterscheidung zwischen der Fläche des Grundstücks Nr. 768, welche bereits mit der Ersatzbauordnung bzw. dem Ersatzzonenplan 1975 der Zone des öffentlichen Interesses zugewiesen worden war, und jener Fläche, bei welcher dies erst im Rahmen der Zonenplanung 1981/82 getan wurde. In Bezug auf Erstere stellte es fest, dass die von den Beschwerdeführern geltend gemachten Ansprüche aus materieller Enteignung verjährt seien. Das Verwaltungsgericht bestätigte diesen Entscheid. Damit beurteilte es abschliessend einen Teil der ursprünglich gestellten Begehren. Da sich dieser Teil unabhängig vom Rest beurteilen lässt, liegt ein Teilentscheid im Sinne von <ref-law> vor (<ref-ruling> E. 1.4.1 S. 144 f.; Urteil 1C_355/2008 vom 28. Januar 2009 E. 1.2; je mit Hinweisen).
Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde unter Vorbehalt der nachfolgenden Erwägung einzutreten.
1.2 Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (<ref-law>). Das setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die Begründungsanforderungen von <ref-law> erfüllt.
Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.6 S. 130; <ref-ruling> E. 2.1 und 2.2 S. 245 f.; je mit Hinweisen).
Die Beschwerdeführer vertreten die Auffassung, das Verwaltungsgericht habe den Anspruch auf rechtliches Gehör (<ref-law>) verletzt, "indem den Beweisanträgen der Beschwerdeführer (Edition von Unterlagen der Stadt Zug und/oder Befragung von damals involvierten Personen/Behörden) nicht oder nicht vollständig stattgegeben wurde". Mit dieser allgemein gehaltenen Kritik zeigen die Beschwerdeführer nicht in hinreichend substanziierter Weise auf, inwiefern der angefochtene Entscheid gegen den verfassungsmässigen Anspruch auf rechtliches Gehör verstösst (<ref-law>). Auf die Rüge ist deshalb nicht einzutreten.
2. 2.1 Die Beschwerdeführer kritisieren die Annahme des Verwaltungsgerichts, dass die Frist für die Verjährung der geltend gemachten Ansprüche aus materieller Enteignung bereits mit Inkrafttreten von Ersatzbauordnung und Ersatzzonenplan am 1. Juli 1975 zu laufen begonnen habe. Es habe sich dabei lediglich um provisorische und vorübergehende raumplanerische Massnahmen gehandelt, denen nicht die Wirkung einer definitiven Eigentumsbeschränkung zugekommen sei. Dafür spreche auch, dass der Ersatzzonenplan vom Regierungsrat ohne Gewährung des rechtlichen Gehörs und nicht im Verfahren des Erlasses eines Zonenplans verfügt worden sei. Der angefochtene Entscheid verletze deshalb Art. 5 RPG (SR 700) und <ref-law> beziehungsweise die entsprechende Bestimmung von Art. 22ter Abs. 3 der Bundesverfassung vom 29. Mai 1874 (aBV). Zudem sei das damalige kantonale Recht willkürlich angewendet worden (<ref-law>).
Die Beschwerdeführer verweisen auf ein Urteil der Schätzungskommission vom 29. Mai 1991. Dieses befasse sich ebenfalls mit der Frage, ab wann eine Eigentumsbeschränkung ihre Wirkung entfalte. Damals sei die Schätzungskommission noch zum (zutreffenden) Schluss gekommen, dass das Inkrafttreten des Ersatzzonenplans 1975 wegen seiner provisorischen Wirkung keine materielle Enteignung bewirkt habe. Indem die Schätzungskommission und in Bestätigung ihres Entscheids auch das Verwaltungsgericht heute anders entschieden, würden sie in unzulässiger Weise ihre Praxis ändern.
2.2 Das Verwaltungsgericht legte dar, nach dem damals gültigen Baugesetz für den Kanton Zug vom 18. Mai 1967 (GS 19, S. 349 ff.; im Folgenden: aBauG) hätten die Gemeinden eine Bauordnung mit Zonenplan erlassen müssen (§ 10 Abs. 1 und § 62 Abs. 1 aBauG). Der Regierungsrat sei ermächtigt gewesen, für Gemeinden, die mit dem Erlass einer Bauordnung im Rückstand waren, einstweilen die Vorschriften und Pläne aufzustellen, die für eine dem öffentlichen Interesse entsprechende Überbauung erforderlich waren (§ 62 Abs. 2 aBauG). Mit Beschluss vom 24. Juni 1975 habe der Regierungsrat die Ersatzbauordnung und den Ersatzzonenplan für die Einwohnergemeinde Zug erlassen und gleichzeitig das Baugesetz für die Stadt Zug vom 27. November 1923 und alle anderen der Ersatzbauordnung widersprechenden Erlasse und Vorschriften aufgehoben. Am 1. Juli 1975 sei die Ersatzbauordnung in Kraft getreten. In der Folge sei der Grosse Gemeinderat der Stadt Zug doch tätig geworden und habe am 30. Juni 1981 den Zonenplan und die Bauordnung der Stadt Zug verabschiedet. Die Erlasse seien in der Folge vom Stimmvolk angenommen und vom Regierungsrat genehmigt worden und seien am 20. April 1982 in Kraft getreten.
Mit der Ersatzbauordnung bzw. dem Ersatzzonenplan 1975 sei der südwestliche Teil des Grundstücks Nr. 768 in die Zone des öffentlichen Interesses eingewiesen worden. Mit dem Zonenplan 1981/82 sei dies zusätzlich mit dem ganzen westlich des Zufahrtssträsschens liegenden Teil des Grundstücks geschehen.
Die Ersatzbauordnung und der Ersatzzonenplan seien auf unbestimmte Zeit erlassen worden, einzig abhängig vom späteren selbständigen Tätigwerden der Einwohnergemeinde Zug. Sie seien deutlich verschieden von den vorläufigen Regelungen gemäss Art. 36 Abs. 2 des damals noch nicht in Kraft stehenden Raumplanungsgesetzes. Kraft kantonalen Rechts hätten sie das bisherige kommunale Recht vollumfänglich ersetzt und für die Betroffenen definitiven Charakter gehabt. Die Ersatzmassnahmen seien bis zu ihrer Ablösung durch eine neue kommunale Ortsplanung unverändert in Kraft geblieben, dies im Gegensatz zu einer nur befristet gültigen Bausperre oder Planungszone.
Aus diesen Gründen habe die Verjährungsfrist für die Ansprüche aus materieller Enteignung am 1. Juli 1975 zu laufen begonnen. Daran ändere auch nichts, dass die Schätzungskommission es in ihrem Beschluss vom 29. Mai 1991 abgelehnt habe, für die Berechnung der Entschädigung aus materieller Enteignung auf jenes Datum abzustellen. Bei der Frage des Beginns der Verjährung zeige sich, dass nicht wie im damaligen Beschluss auf das Beurteilungskriterium der Zumutbarkeit der Eigentumsbeschränkung abgestellt werden könne. Dies hätte eine grosse Rechtsunsicherheit zur Folge. Schliesslich sei der Vorwurf der unzulässigen Praxisänderung unbegründet. Soweit man überhaupt von einer Praxisänderung sprechen wolle, so seien die Voraussetzungen dafür erfüllt, entspreche doch die heutige Auffassung dem Gesetz deutlich besser. Es handle sich zudem beim Beschluss vom 29. Mai 1991 um einen singulären Entscheid. Insgesamt erschienen Rechtssicherheit und Rechtsgleichheit nicht beeinträchtigt.
Aus diesen Gründen habe die Verjährungsfrist für die Ansprüche aus materieller Enteignung am 1. Juli 1975 zu laufen begonnen. Daran ändere auch nichts, dass die Schätzungskommission es in ihrem Beschluss vom 29. Mai 1991 abgelehnt habe, für die Berechnung der Entschädigung aus materieller Enteignung auf jenes Datum abzustellen. Bei der Frage des Beginns der Verjährung zeige sich, dass nicht wie im damaligen Beschluss auf das Beurteilungskriterium der Zumutbarkeit der Eigentumsbeschränkung abgestellt werden könne. Dies hätte eine grosse Rechtsunsicherheit zur Folge. Schliesslich sei der Vorwurf der unzulässigen Praxisänderung unbegründet. Soweit man überhaupt von einer Praxisänderung sprechen wolle, so seien die Voraussetzungen dafür erfüllt, entspreche doch die heutige Auffassung dem Gesetz deutlich besser. Es handle sich zudem beim Beschluss vom 29. Mai 1991 um einen singulären Entscheid. Insgesamt erschienen Rechtssicherheit und Rechtsgleichheit nicht beeinträchtigt.
2.3 2.3.1 Die Beschwerdeführer berufen sich primär auf die Bestimmungen von <ref-law> bzw. Art. 22ter Abs. 3 aBV und Art. 5 RPG. In Bezug auf die Pflicht, Eigentumsbeschränkungen, die einer Enteignung gleichkommen, voll zu entschädigen, statuieren diese Bestimmungen dasselbe (ENRICO RIVA, in: Kommentar zum Bundesgesetz über die Raumplanung, N. 2 zu Art. 5 RPG; BERNHARD WALDMANN/PETER HÄNNI, Raumplanungsgesetz, 2006, N. 3 zu Art. 5 RPG).
Für die Ausgestaltung einer Verjährungsfrist für Ansprüche aus materieller Enteignung ist in erster Linie der kantonale Gesetzgeber zuständig. Schweigt das kantonale Recht zu dieser Frage, so beträgt die Frist zehn Jahre und beginnt mit dem Inkrafttreten der Eigentumsbeschränkung zu laufen (<ref-ruling> E. 1b S. 370; <ref-ruling> E. 4c S. 338 und E. 5 S. 339 f.; je mit Hinweisen). Dass mangels einer kantonalen Vorschrift vorliegend deshalb von einer Verjährungsfrist von zehn Jahren auszugehen ist, ist nicht umstritten. Streitig ist indessen, wann diese zu laufen begonnen hat.
2.3.2 Ob die Ersatzmassnahmen des Kantons Zug, welche am 1. Juli 1975 in Kraft traten, zu einer materiellen Enteignung führten, bestimmt sich in erster Linie nach Bundesrecht. Zwar waren die Kantone vor Erlass des Raumplanungsgesetzes frei, den Begriff der materiellen Enteignung weiter zu fassen, doch durften sie umgekehrt nicht hinter die Mindestgarantie von Art. 22ter Abs. 3 aBV zurücktreten. Diese Verfassungsbestimmung trat am 11. Dezember 1969 in Kraft, ihr Inhalt ergab sich indes schon vorher aus ungeschriebenem Verfassungsrecht des Bundes (<ref-ruling> E. 1a S. 383 f.; <ref-ruling> E. 3 S. 115; je mit Hinweisen).
Eine materielle Enteignung liegt danach insbesondere vor, wenn dem Eigentümer der bisherige oder ein voraussehbarer künftiger Gebrauch einer Sache untersagt oder in einer Weise eingeschränkt wird, die besonders schwer wiegt, weil der betroffenen Person eine wesentliche aus dem Eigentum fliessende Befugnis entzogen wird (eingehender: <ref-ruling> E. 2 S. 730; Urteil 1C_449/2009 vom 26. Mai 2009 E. 5 mit Hinweisen). Im vorliegenden Fall wurde mit der Ersatzbauordnung bzw. dem Ersatzzonenplan von 1975 der fragliche Grundstücksteil der Zone des öffentlichen Interesses zugewiesen. Der kommunale Zonenplan 1981/82, der dieser Zone noch weitere Gebiete zuwies, änderte insofern nichts. Die Beschwerdeführer machen jedoch wie erwähnt geltend, erst der kommunale Zonenplan habe eine definitive Eigentumsbeschränkung bewirkt.
Bei einer zeitlich befristeten Beschränkung der Nutzungsmöglichkeit eines Grundstücks nimmt das Bundesgericht nur dann eine enteignungsgleiche Wirkung an, wenn diese länger andauert, wobei letztlich die konkreten Umstände des Einzelfalls massgebend sind (vgl. etwa <ref-ruling> E. 9 S. 495 ff.; <ref-ruling> E. 6c S. 214 f.; <ref-ruling> E. 4a S. 22 f.; Urteil 1C_510/2009 vom 14. Juli 2009 E. 4.1; je mit Hinweisen). Eine derartige zeitlich befristete Beschränkung bewirken insbesondere plansichernde Massnahmen nach Art. 27 RPG und entsprechende Instrumente des kantonalen Rechts (v.a. die Bausperre). Diese bezwecken, dass nichts unternommen wird, was die Nutzungsplanung erschweren könnte (zur Publikation bestimmtes Urteil 1C_501/2009 vom 4. Januar 2010 E. 2.2; <ref-ruling> E. 2.5 S. 242 mit Hinweis; WALDMANN/HÄNNI, a.a.O., N. 1 und N. 35 f. zu Art. 27 RPG). Von plansichernden Massnahmen unterscheiden sich Ersatzmassnahmen, wie sie § 62 Abs. 2 aBauG vorsah, dadurch, dass sie nicht auf eine negative Wirkung beschränkt sind. Während plansichernde Massnahmen die Nutzungsplanung erschwerende Veränderungen in der Planungszone verhindern sollen, entfalten Ersatzmassnahmen nach § 62 Abs. 2 aBauG in dem Sinne eine positive Wirkung, als gestützt auf sie Baugesuche bewilligt werden können. Abgesehen davon, dass die Ersatzbauordnung und der Ersatzzonenplan von 1975 nur so lange galten, bis die Gemeinde ihre Planungsobliegenheit selbst wahrnahm, und in diesem Sinne "einstweilen" (§ 62 Abs. 2 aBauG) erlassen wurden, unterschied sie somit inhaltlich nichts von einer kommunalen Nutzungsplanung. Da aber gerade auch eine kommunale Nutzungsplanung nur bis zu ihrer Revision gilt, ist ihr eine kantonale Ersatzmassnahme, wie sie hier vorliegt, in Bezug auf die Frage der materiellen Enteignung gleichzustellen (vgl. Art. 21 Abs. 2 RPG, wonach Nutzungspläne geprüft und nötigenfalls angepasst werden, wenn sich die Verhältnisse erheblich verändert haben).
Zusammenfassend lässt sich deshalb festhalten, dass die Ersatzbauordnung und der Ersatzzonenplan von 1975 eine zeitlich nicht befristete Beschränkung der Nutzungsmöglichkeit darstellten und die Vorinstanz kein Bundesrecht verletzte, wenn sie davon ausging, dass im Zeitpunkt ihres Inkrafttretens die Verjährung der Ansprüche der Beschwerdeführer aus materieller Enteignung zu laufen begann.
2.3.3 Weiter ist zu prüfen, ob die Beschwerdeführer Recht haben, wenn sie in Bezug auf das Urteil vom 29. Mai 1991 der Schätzungskommission von einer unzulässigen Praxisänderung sprechen. Gemäss der Rechtsprechung des Bundesgerichts lässt sich eine Änderung der Praxis regelmässig nur begründen, wenn die neue Lösung besserer Erkenntnis der ratio legis, veränderten äusseren Verhältnissen oder gewandelter Rechtsanschauung entspricht; andernfalls ist die bisherige Praxis beizubehalten. Eine Praxisänderung muss sich deshalb auf ernsthafte sachliche Gründe stützen können, die - vor allem im Interesse der Rechtssicherheit - umso gewichtiger sein müssen, je länger die als falsch oder nicht mehr zeitgemäss erachtete Rechtsanwendung gehandhabt worden ist (<ref-ruling> E. 3 S. 82; <ref-ruling> E. 3.2 S. 85; <ref-ruling> E. 2.3 S. 338; je mit Hinweisen).
Im Urteil der Schätzungskommission vom 29. Mai 1991 ging es um den Bemessungszeitpunkt für die Entschädigung für das heimgeschlagene Grundstück Nr. 3753, welches 1984 vom Grundstück Nr. 768 abparzelliert worden war und damit ebenfalls den Beschwerdeführern gehört hatte. Ausschlaggebend war wie hier die Frage nach dem Zeitpunkt der Rechtskraft der Eigentumsbeschränkung (vgl. RIVA, a.a.O., N. 183 zu Art. 5 RPG). Nach dem Gesagten widerspricht jedoch die Auffassung, welche dem Urteil der Schätzungskommission vom 29. Mai 1991 zugrunde lag, dem Bundesrecht. Es gab mithin ernsthafte sachliche Gründe, auf diese Auffassung zurückzukommen. Die damalige, nun als falsch erkannte Auslegung soll zudem singulär gewesen sein, so dass die Rechtssicherheit nicht als beeinträchtigt erscheint. Zu prüfen wäre indessen, ob nicht der Grundsatz des Vertrauensschutzes dem Abstellen auf den früheren Beginn der Verjährungsfrist entgegensteht (vgl. BGE <ref-ruling> E. 3.2 S. 85; <ref-ruling> E. 5.1 S. 159; Urteil 2C_421/2007 vom 21. Dezember 2007 E. 3 in: StR 63/2008 S. 545; je mit Hinweisen). Dies ist jedoch nur dann angezeigt, wenn die Verjährungsfrist nicht ohnehin bereits vor dem 29. Mai 1991 abgelaufen war, denn eine bereits abgelaufene Verjährungsfrist konnte durch das Urteil der Schätzungskommission nicht wieder aufleben. Wie es sich damit verhält, ist im Folgenden zu prüfen.
3. 3.1 Die Beschwerdeführer sind der Ansicht, die Verjährungsfrist sei rechtzeitig unterbrochen worden. Sie weisen auf ein Schreiben vom 30. November 1983 von Rechtsanwalt Rolf Schweiger an den Stadtrat Zug hin und machen weiter geltend, sie seien ab 1975 und intensiv ab 1980 im Gespräch mit den Exekutivbehörden der Stadt Zug über das Geschick des Guggihügels gewesen.
3.2 Die Verjährung ist eine Rechtsfigur, die als allgemeiner Rechtsgrundsatz im gesamten öffentlichen Recht gilt (<ref-ruling> E. 6b S. 627; vgl. auch E. 2.3.1 hiervor). Gemäss der bundesgerichtlichen Rechtsprechung kann die Verjährung öffentlich-rechtlicher Ansprüche unterbrochen werden. Falls dem gesetzten Recht dazu nichts zu entnehmen ist, genügt dafür neben den in <ref-law> genannten Handlungen jeder Akt, mit dem die Forderung gegenüber dem Schuldner in geeigneter Weise geltend gemacht wird. Insbesondere reicht eine an den Verpflichteten gerichtete schriftliche Forderungserklärung für die Verjährungsunterbrechung aus. Eine bloss mündliche Geltendmachung genügt jedenfalls dann, wenn sie schriftlich bestätigt wird. Im Weiteren dürfen an den Inhalt der Erklärung des Entschädigungsberechtigten, wie das Bundesgericht im Zusammenhang mit dem Zinsenlauf ausgeführt hat, keine allzu hohen Anforderungen gestellt werden. Die Angabe eines bestimmten Forderungsbetrags wird nicht verlangt. Es muss aus der Erklärung für das ersatzpflichtige Gemeinwesen nur (aber immerhin) unmissverständlich hervorgehen, dass der Grundeigentümer um Vergütung für den planerischen Eingriff ersucht (Urteil 1A.15/1997 vom 25. August 1997 E. 3, in: ZBl 99/1998 S. 489; <ref-ruling> E. 4.3.1 S. 583; je mit Hinweisen; vgl. auch <ref-ruling> E. 3b S. 33; ATTILIO GADOLA, Verjährung und Verwirkung im öffentlichen Recht, AJP 1995 S. 54).
3.3 In den Akten befindet sich ein Schreiben des Stadtrats Zug vom 25. November 1980. Darin bestätigte der Stadtrat dem Rechtsvertreter der Gesuchsteller, dass dieser das Begehren gestellt habe, es sei eine Entschädigung für materielle Enteignung für jene Fläche der Parzelle Nr. 768 zu leisten, welche gemäss dem Ersatzzonenplan in der Zone des öffentlichen Interesses liege. Da die Voraussetzungen für eine formelle Enteignung oder für die Geltendmachung des Heimschlagrechts gegeben seien, entfalle jedoch eine Entschädigung aus materieller Enteignung. Der Stadtrat wies weiter darauf hin, dass der Rechtsvertreter das Heimschlagrecht für einen 10'911 m2 grossen Abschnitt der Parzelle geltend gemacht habe und erklärte, die Stadt sei bereit, die Fläche zu kaufen.
Mit Schreiben vom 30. November 1983 teilte der Rechtsvertreter der Beschwerdeführer dem Stadtrat mit, dass diese unter den im Schreiben aufgeführten Bedingungen damit einverstanden seien, den grösseren Teil des der Zone des öffentlichen Interesses zugewiesenen Anteils von Parzelle Nr. 768 an die Einwohnergemeinde Zug heimzuschlagen. Hinsichtlich des östlich bzw. südöstlich der in einem beigelegten Plan mit oranger Farbe bezeichneten Linie gelegenen Teils des Grundstücks Nr. 768 möchten sich die Erben vorerst eine Entscheidung noch vorbehalten. Es werde erwogen, bezüglich eines Teils dieses Landstücks ein Umzonungsbegehren zu stellen und/oder eine Entschädigung zufolge materieller Enteignung geltend zu machen. Diesbezügliche Gespräche würde er mit dem Stadtrat zu einem späteren Zeitpunkt aufnehmen.
3.4 Das Verwaltungsgericht erwog, die Stadt verfüge nach ihren glaubwürdigen Ausführungen über keine Aktennotizen oder Protokolle über die Gespräche mit den Beschwerdeführern aus jener Zeit. Die von den Beschwerdeführern vorgebrachten Verhandlungen mit dem Stadtrat im Zusammenhang mit dem Heimschlagsverfahren seien mit dem Urteil der Schätzungskommission vom 29. Mai 1991 rechtskräftig abgeschlossen worden. Wenn sich die Gesuchsteller im Schreiben vom 30. November 1983 eine "Entscheidung noch vorbehielten", so komme dies nicht einer verjährungsunterbrechenden Anmeldung einer Forderung aus materieller Enteignung gleich. Es bestünden keine Beweise, dass im Rahmen der den Heimschlag betreffenden Gespräche auch über Ansprüche aus materieller Enteignung betreffend die hier umstrittene Fläche gesprochen worden sei. Wenn der Antwort des Stadtrats vom 25. November 1980 auf die Eingabe der Beschwerdeführer eine verjährungsunterbrechende Wirkung zugesprochen würde, so wäre die mit Eingabe vom 16. April 1992 geltend gemachte Entschädigung aus materieller Enteignung trotzdem bereits (wieder) verjährt gewesen.
3.5 Die Beschwerdeführer machen nicht geltend, vom Stadtrat hingehalten worden zu sein. Die Einrede der Verjährung erscheint deshalb nicht als treuwidrig (<ref-law>). Entscheidend ist deshalb, ob die Beschwerdeführer seit Mitte April 1982 (zehn Jahre vor der Geltendmachung von Entschädigungsansprüchen mit Schreiben vom 16. April 1992) unmissverständlich erklärt haben, eine Vergütung für den planerischen Eingriff zu verlangen. Mit dem Schreiben vom 30. November 1983 äusserten sie, wie bereits erwähnt, dass sie sich "eine Entscheidung noch vorbehalten möchten" und erwägen würden, "ein Umzonungsbegehren zu stellen und/oder eine Entschädigung zufolge materieller Enteignung geltend zu machen". Diesbezügliche Gespräche würden mit dem Stadtrat zu einem späteren Zeitpunkt aufgenommen. Mit diesen Ausführungen wurde keine Entschädigungsforderung geltend gemacht. Die Beschwerdeführer fassten lediglich deren Möglichkeit ins Auge und erwogen auch ein Umzonungsbegehren, weshalb sie auf mögliche spätere Gespräche verwiesen.
3.6 Aus dem Gesagten folgt, dass allfällige Ansprüche aus materieller Enteignung am 16. April 1992 und auch im Zeitpunkt der Fällung des Urteils vom 29. Mai 1991 durch die Schätzungskommission (vgl. E. 2.3.3 hiervor) bereits verjährt waren. Die Rügen der Beschwerdeführer erweisen sich damit als unbegründet.
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Diesem Ausgang des Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Weder die Beschwerdeführer noch die Einwohnergemeinde Zug, die in ihrem amtlichen Wirkungskreis obsiegt hat, haben Anspruch auf eine Parteientschädigung (Art. 68 Abs. 2 und 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Einwohnergemeinde Zug, der Schätzungskommission und dem Verwaltungsgericht des Kantons Zug, Verwaltungsrechtliche Kammer, sowie dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 13. August 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Aemisegger Dold