A.

A.a A.C. und B.C. (Beschwerdeführer) sind Eigentümer einer Wohn- und Geschäftsliegenschaft an der Via D./Via E. in F. (Parzelle Nr. 1 des Grundbuches der Gemeinde F.). Ausserdem waren sie Berechtigte aus einem selbständigen und dauernden Baurecht (Parzelle Nr. 2 des Grundbuches der Gemeinde F.) auf Errichtung einer Parkplatzanlage auf dem belasteten, ebenfalls an der Via E. befindlichen Grundstück (Parzelle Nr. 3 des Grundbuches der Gemeinde F.). Bis zur Begründung von Stockwerkeigentum und der anschliessenden Überbauung mit einem Wohn- und Geschäftshaus samt einer sechsstöckigen Tiefgarage war die X. AG (Beschwerdegegnerin) Alleineigentümerin des baurechtsbelasteten Grundstücks (Parzelle Nr. 3).

A.b Am 20. Juni 2003 unterzeichneten die Beschwerdeführer auf der einen und H. auf der anderen Seite einen Vorvertrag auf Abschluss einer Vereinbarung über die Aufhebung eines Baurechts. In den Vorbemerkungen der Vertragsurkunde hielten sie nicht nur die oben erwähnten Berechtigungen an der Parzelle Nr. 3 fest (Eigentum, Baurecht), sondern erklärten darüber hinaus, dass Dr. H. einen Anspruch auf den Erwerb sämtlicher Aktien der Beschwerdegegnerin habe und befugt sei, die Rechte aus dem Vorvertrag gegen Übernahme der entsprechenden Pflichten auf diese oder eine andere Gesellschaft zu übertragen.

A.c Für den Fall, dass die in den Vorbemerkungen umschriebene Voraussetzung erfüllt werde, trafen die Parteien unter anderem die folgenden Vereinbarungen: Aufhebung des auf der Parzelle Nr. 3 lastenden Baurechts gegen Überlassung von zwanzig Autoabstellplätzen durch die Beschwerdegegnerin in der von ihr auf der Parzelle Nr. 3 geplanten Tiefgarage; Verpflichtung der Beschwerdegegnerin, bei der Überbauung der Parzelle Nr. 3 eine Höhenbeschränkung von 8,5 Metern ab einem bestimmten Referenzpunkt (1819,498 m.ü.M.) einzuhalten; gemeinsame Grundbuchanmeldung durch die beiden Rechtsvertreter und gleichzeitige Grundbucheintragung der Verträge auf Aufhebung des Baurechts und auf Überlassung der zwanzig Autoabstellplätze.

A.d Am 30. März 2004 unterzeichneten die Beschwerdeführer und die Beschwerdegegnerin einen Vertrag auf Aufhebung des Baurechts, wobei die Beschwerdegegnerin durch die kollektiv zeichnungsberechtigten Angehörigen des Verwaltungsrates H. (Präsident) und I. (Mitglied) vertreten wurde. Die Parteien hielten in der öffentlichen Urkunde fest, dass sich die Beschwerdeführer bereits im Vorvertrag vom 20. Juni 2003 zur Aufhebung des auf der Parzelle Nr. 3 lastenden Baurechts verpflichtet hätten, und zwar Zug um Zug gegen Übertragung des Eigentums an zwanzig im Rahmen der geplanten Überbauung der Parzelle Nr. 3 erst noch zu errichtenden Autoabstellplätzen. Nach den weiteren Ausführungen im Vertrag vom 30. März 2004 war zu diesem Zeitpunkt an der Parzelle Nr. 3 noch kein Stockwerkeigentum begründet worden, weshalb die Beschwerdegegnerin vorerst nicht in der Lage war, die genannte und von ihr ausdrücklich als eigene Verpflichtung anerkannte Eigentumsverschaffung zu erfüllen. Um den Baubeginn nicht zu verzögern, erklärten sich die Beschwerdeführer gegen Einräumung finanzieller Sicherheiten trotzdem damit einverstanden, dass das Baurecht bereits auf den 1. April 2004 aufgehoben und die Baurechtsparzelle Nr. 2 im Grundbuch gelöscht werde.

A.e Die Dachoberkante des in der Folge auf der Parzelle Nr. 3 errichteten Wohn- und Geschäftshauses samt Tiefgarage liegt gerade noch innerhalb der im Vorvertrag vom 20. Juni 2003 festgelegten Bauobergrenze von 1827,998 m.ü.M., drei Aufbauten, die offenbar Liftmotoren und Kamine enthalten, hingegen nicht mehr.

B.

B.a Am 31. Oktober 2006 erhoben die Beschwerdeführer beim Bezirksgericht Maloja Klage mit folgenden Begehren: Erstens sei die beklagte X. AG unter Strafandrohung zu verpflichten, die Dachaufbauten auf dem Gebäude der Parzelle Nr. 3 innert angemessener Frist zu beseitigen, soweit sie die vereinbarte Höherbaubeschränkung verletzen; zweitens sei das Grundbuchamt G. anzuweisen, die Höherbaubeschränkung zulasten des Grundstücks Parzelle Nr. 3 und zugunsten der Parzelle Nr. 1 als Grunddienstbarkeit im Grundbuch einzutragen; drittens sei die Beklagte eventualiter zu verpflichten, Schadenersatz von Fr. 300'000.-, evtl. nach richterlichem Ermessen, zuzüglich Zins zu bezahlen. In ihrer Prozessantwort schloss die Beschwerdegegnerin auf Abweisung der Klage. Anlässlich der erstinstanzlichen Hauptverhandlung zogen die Beschwerdeführer ihr Begehren auf Eintragung einer Grunddienstbarkeit vorbehaltlos zurück.

B.b Mit Urteil vom 3. Juli 2007 hiess das Bezirksgericht Maloja die Klage gut und verurteilte die Beschwerdegegnerin, die Dachaufbauten zu beseitigen. Dagegen erhob die Beschwerdegegnerin Berufung beim Kantonsgericht von Graubünden mit dem Begehren, das angefochtene Urteil aufzuheben und die Klage abzuweisen.

B.c Mit Urteil vom 12. Februar 2008 hiess das Kantonsgericht die Berufung unter Abweisung des Beseitigungsbegehrens teilweise gut und wies die Sache zur Behandlung des eventualiter gestellten Schadenersatzbegehrens sowie zur Neubeurteilung der Kosten- und Entschädigungsfolgen an die Vorinstanz zurück. Das Kantonsgericht kam zum Schluss, dass die Beschwerdegegnerin zwar die Höherbaubeschränkung verletzt habe, weshalb das Beseitigungsbegehren an sich gutzuheissen wäre. Da aber die Liegenschaft Parzelle Nr. 3 zu Stockwerkeigentum aufgeteilt sei, die Dachaufbauten dem gemeinschaftlichen Bereich zuzuordnen und daher nicht der Ausscheidung zu Sonderrecht zugänglich seien, könne die Beschwerdegegnerin die Beseitigung nicht von sich aus an die Hand nehmen; die nötigen Mehrheiten dafür werde sie bei den übrigen Stockwerkeigentümern nicht finden. Die Beseitigungsleistung erweise sich daher als unmöglich, weshalb das Hauptbegehren abgewiesen werden müsse. Da die Vorinstanz sich noch nicht mit dem eventualiter gestellten Schadenersatzbegehren habe befassen müssen, sei die Streitsache zur Beurteilung dieses Begehrens an die Vorinstanz zurückzuweisen.

C. Mit Beschwerde in Zivilsachen vom 1. September 2008 beantragen die Beschwerdeführer dem Bundesgericht, es sei das Urteil des Kantonsgerichts von Graubünden aufzuheben und die Beschwerdegegnerin unter Strafandrohung zu verurteilen, die bereits errichteten Dachaufbauten auf dem Gebäude der Parzelle Nr. 3 (Grundbuch F.) innert angemessener und richterlich anzusetzender Frist zu entfernen, soweit sie die vereinbarte privatrechtliche Baubeschränkung (Höhenbeschränkung auf 1827,998 m.ü.M.) verletzen.

D. Die Beschwerdegegnerin und das Kantonsgericht schliessen in ihren Vernehmlassungen auf Abweisung der Beschwerde, sofern auf sie einzutreten sei.

Das Bundesgericht weist die Beschwerde ab, soweit es darauf eintritt.

1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (Art. 29 Abs. 1 BGG; BGE 134 III 520 E. 1 S. 521; BGE 133 III 462 E. 2 S. 465; je mit Hinweisen).

1.1 Gegenstand des Verfahrens bildet eine Zivilsache (Art. 72 Abs. 1 BGG). Die Rechtsbegehren der Beschwerdeführer sind im kantonalen Verfahren nicht vollständig geschützt worden (Art. 76 Abs. 1 BGG), das Vermögensinteresse bezüglich des vorliegend verlangten Abbaus der Dachaufbauten erreicht offensichtlich den massgebenden Streitwert von Fr. 30'000.- (Art. 51 i.V.m. Art. 74 Abs. 1 lit. b BGG). Die Beschwerdefrist ist eingehalten (Art. 100 Abs. 1 BGG i.V.m. Art. 46 Abs. 1 lit. b BGG). Zu prüfen bleibt, ob der angefochtene Entscheid ein beschwerdefähiges Anfechtungsobjekt bildet.

1.2 Die Beschwerde ist in der Regel erst gegen Endentscheide der oberen kantonalen Gerichte zulässig (Art. 90 BGG). Gemeint sind Entscheide, die den Prozess beenden (BGE 133 III 393 E. 4 S. 395). Vorliegend hat das Kantonsgericht nur über das Hauptbegehren entschieden und die Sache an die Vorinstanz zum Entscheid über das Eventualbegehren zurückgewiesen. Rückweisungsentscheide schliessen das Verfahren nicht ab und sind somit nach der Regelung des BGG keine Endentscheide (BGE 134 II 124 E. 1.3 S. 127; BGE 133 V 477 E. 4.2 S. 481 f. mit Hinweisen). Es handelt sich vielmehr um Zwischenentscheide, die nur unter den Voraussetzungen von Art. 93 Abs. 1 BGG selbständig angefochten werden können (BGE 133 V 477 E. 4.2 S. 481). Der angefochtene Entscheid enthält indessen nicht nur einen Rückweisungsentscheid, sondern auch einen materiellen Entscheid über einen Teil des Streitgegenstands. Angefochten ist denn auch nur die Abweisung des Hauptbegehrens. Es ist daher zu prüfen, ob das vorinstanzliche Urteil einen beschwerdefähigen Teilentscheid im Sinne von Art. 91 lit. a BGG darstellt.

1.2.1 Ein Teilentscheid ist eine Variante des Endentscheids. Mit ihm wird über eines oder einige von mehreren Rechtsbegehren (objektive oder subjektive Klagenhäufung) abschliessend befunden (BGE 134 III 426 E 1.1 S. 428; BGE 133 V 477 E. 4.1.2 S. 480; Botschaft vom 28. Februar 2001 zur Totalrevision der Bundesrechtspflege [nachfolgend: Botschaft BGG], BBl 2001 4202 ff., 4332 Ziff. 4.1.4.1). Es handelt sich dabei nicht um verschiedene materiellrechtliche Teilfragen eines Rechtsbegehrens, sondern um verschiedene Rechtsbegehren (BGE 133 V 477 E. 4.1.2 S. 480). Ein Entscheid, der nur einen Teil der gestellten Begehren behandelt, ist jedoch nur dann ein vor Bundesgericht anfechtbarer Teilentscheid, wenn diese Begehren unabhängig von den anderen beurteilt werden können (Art. 91 lit. a BGG).

1.2.2 Unabhängigkeit im Sinne von Art. 91 lit. a BGG ist zum einen so zu verstehen, dass die gehäuften Begehren auch Gegenstand eines eigenen Prozesses hätten bilden können (Botschaft BGG, BBl 2001 4202 ff., 4332 Ziff. 4.1.4.1; so auch schon die Praxis unter der Herrschaft des Bundesgesetzes über die Organisation der Bundesrechtspflege [OG], statt aller BGE 131 III 667 E. 1.3 S. 669 f. mit ausführlichen Hinweisen auf die bundesgerichtliche Praxis; FELIX UHLMANN, in: Basler Kommentar, Bundesgerichtsgesetz, 2008, N. 5 zu Art. 91 BGG). Vorliegend haben die Beschwerdeführer im Hauptbegehren einen Anspruch auf Beseitigung des vertragswidrigen Zustands und im Eventualbegehren einen Anspruch auf Schadenersatz geltend gemacht. Zwar hängen diese Ansprüche gleichermassen von der Vorfrage der Vertragsverletzung ab, sind aber auf eine andere Rechtsfolge ausgerichtet. Die Ansprüche sind somit nicht identisch, weshalb die beiden eventualgehäuften Begehren auch Gegenstand zweier separater Prozesse hätten bilden können.

1.2.3 Zum anderen erfordert die Unabhängigkeit, dass der angefochtene Entscheid einen Teil des gesamten Prozessgegenstands abschliessend beurteilt, so dass keine Gefahr besteht, dass das Schlussurteil über den verbliebenen Prozessgegenstand im Widerspruch zum bereits rechtskräftig ausgefällten Teilurteil steht (in diesem Sinne auch HANS PETER WALTER, Das Teilurteil vor Bundesgericht, in: Der Weg zum Recht, 2008, S. 248). Bei Eventualhäufungen bewirkt die prozessuale Verknüpfung der Urteile über das Haupt- und das Eventualbegehren, dass kein Widerspruch zwischen dem Teil- und Schlussurteil entstehen kann, da der allenfalls separat auszufällende Entscheid über das Eventualbegehren nur dann Bestand hat, wenn die Abweisung des Hauptbegehrens in Rechtskraft erwächst. Eine selbständig eröffnete Abweisung des Hauptbegehrens ist daher grundsätzlich als anfechtungspflichtiger Teilentscheid zu betrachten (vgl. auch schon WALTHER WÜTHRICH, Teilklage und Teilurteil, 1952, S. 38; zur Obliegenheit der Anfechtung BGE 134 III 426 E. 1.1 S. 428). Der vorliegend angefochtene Entscheid ist damit ein beschwerdefähiger Teilentscheid gemäss Art. 91 lit. a BGG.

(...)

3. In materiellrechtlicher Hinsicht werfen die Beschwerdeführer der Vorinstanz vor, sie habe den Begriff der nachträglichen Leistungsunmöglichkeit im Sinne des Art. 97 Abs. 1 OR verkannt. Die Erbringung der Beseitigungsleistung sei nicht unmöglich.

3.1 Kann die Erfüllung einer Forderung nach Vertragsschluss überhaupt nicht mehr bewirkt werden, liegt ein Fall nachträglicher Unmöglichkeit vor. Dabei ist zwischen objektiver und subjektiver Unmöglichkeit zu unterscheiden. Erstere ist gegeben, wenn niemand mehr in der Lage ist, die Forderung zu erfüllen; Letztere, wenn die Erfüllung zwar an sich möglich, aber der Schuldner dazu ausserstande ist. Die Leistung ist namentlich dann subjektiv unmöglich, wenn nach Treu und Glauben im Verkehr dem Schuldner die weitere Erfüllung nicht mehr zumutbar ist (BGE 82 II 332 E. 5 S. 338). Dabei genügt jedoch nicht, dass die Leistung bloss erheblich erschwert ist; das Leistungshindernis muss sich für den Schuldner vielmehr als geradezu unüberwindbar herausstellen. Nach der Rechtsprechung des Bundesgerichts kann das Leistungshindernis in der nachträglich weggefallenen Verfügungsmacht des Schuldners über den Leistungsgegenstand bestehen (BGE 84 II 6 E. 1 S. 10). Dabei ist einschränkend zu präzisieren, dass das Leistungshindernis für den Schuldner erst dann unüberwindbar wird, wenn dieser überhaupt keine Möglichkeit mehr hat, die Verfügungsmacht zurückzuerlangen oder die zur Leistungserfüllung notwendigen Zustimmungen der Verfügungsberechtigten einzuholen. Dies entspricht auch der Rechtsprechung und Lehre zu mit Art. 97 OR vergleichbaren Regeln in Nachbarrechtsordnungen (Urteil des deutschen Bundesgerichtshofs vom 26. März 1999, in: NJW 1999 S. 2034 ff.; WOLFGANG ERNST, in: Münchener Kommentar zum Bürgerlichen Gesetzbuch, Bd. II, 5. Aufl. München 2007, N. 53 zu § 275 BGB; STAUDINGER/LÖWISCH, Kommentar zum Bürgerlichen Gesetzbuch, Stand: Januar 2004, N. 61 zu § 275 BGB; für das italienische Recht DANIELA MEMMO, in: Commentario breve al Codice civile, Galgano [Hrsg.], Piacenza 2006, N. 6 zu Art. 1218 CCit, wonach subjektive Unmöglichkeit erst dann vorliegt, wenn das Leistungshindernis vom Schuldner überhaupt nicht mehr beseitigt werden kann; für das österreichische Recht RUDOLF REISCHAUER, in: Kommentar zum Allgemeinen bürgerlichen Gesetzbuch, Rummel [Hrsg.], Bd. I, 2. Aufl., Wien 1990, N. 10 zu § 920 ABGB).

3.2 Vorliegend ist nicht bestritten, dass die Dachaufbauten, deren Beseitigung die Beschwerdeführer verlangen, gemeinschaftliche Bauteile der im Stockwerkeigentum stehenden Liegenschaft sind. Ein Stockwerkeigentümer ist zwar in der baulichen Ausgestaltung seiner eigenen, d.h. zu Sonderrecht ausgeschiedenen Räume frei, darf jedoch keine gemeinschaftlichen Bauteile, Anlagen und Einrichtungen beschädigen oder in ihrer Funktion und äusseren Erscheinung beeinträchtigen (Art. 712a Abs. 2 ZGB). Bei dieser Unterlassungspflicht handelt es sich um eine unmittelbare gesetzliche Eigentumsbeschränkung (MEIER-HAYOZ/REY, Berner Kommentar, 3. Aufl. 1988, N. 72 zu Art. 712a ZGB). Befugnisse des Stockwerkeigentümers zu eigenmächtigen Umbauarbeiten an gemeinschaftlichen Teilen gibt es auch dann nicht, wenn damit keine Beschädigungen oder Beeinträchtigungen verbunden wären. Dies wäre mit der gesetzlichen Zuständigkeitsordnung in Bezug auf die gemeinschaftlichen Teile betreffenden Verwaltungshandlungen und baulichen Massnahmen nicht vereinbar (Art. 712a Abs. 2 ZGB). Diesbezüglich wird in Art. 712g Abs. 1 ZGB auf die Bestimmungen über das Miteigentum (Art. 647a-e ZGB) verwiesen. Demnach bedürfen notwendige bauliche Massnahmen, d.h. solche, die für die Erhaltung des Wertes und der Sache nötig sind, der Zustimmung der Mehrheit aller Miteigentümer, soweit sie nicht als gewöhnliche Verwaltungshandlungen von jedem Einzelnen vorgenommen werden dürfen (Art. 647c ZGB). Nützliche bauliche Massnahmen bedürfen dagegen der Zustimmung der Mehrheit aller Miteigentümer, die zugleich den grösseren Teil der Sache vertritt (Art. 647d Abs. 1 ZGB), und der Verschönerung und Bequemlichkeit dienende Massnahmen ebenfalls der Zustimmung aller Miteigentümer (Art. 647e Abs. 1 ZGB).

Aus Sicht der Stockwerkeigentümerschaft erscheint der Abbau der Dachaufbauten nicht notwendig im Sinne von Art. 647c ZGB, weshalb die Beschwerdegegnerin die Beseitigung nicht gestützt auf Art. 647 Abs. 2 Ziff. 1 ZGB verlangen kann. In welche der anderen Kategorien baulicher Massnahmen der Abbau der Dachaufbauten einzustufen wäre, ist vorliegend unerheblich, da die Beschwerdegegnerin stets mindestens die Zustimmung einer Mehrheit aller Stockwerkeigentümer bräuchte. Diese könnte nur dann erzwungen werden, wenn die schuldrechtliche Höherbaubeschränkung auch die anderen Stockwerkeigentümer binden würde. Das scheitert indessen daran, dass eine obligatorische Unterlassungspflicht nur relative Wirkung entfaltet und weder aus den Feststellungen der Vorinstanz ersichtlich ist noch von den Parteien jemals behauptet wurde, dass diese auch den anderen Stockwerkeigentümern vertraglich überbunden worden wäre. Fest steht zudem, dass die vertragliche Höherbaubeschränkung nicht in eine (absolut wirkende) Grunddienstbarkeit überführt wurde. Die Beschwerdegegnerin griffe also in dingliche Rechtspositionen der anderen Stockwerkeigentümer ein, wenn sie die Dachaufbauten eigenmächtig abbauen liesse. Sie würde sich dabei nicht nur privatrechtlich, sondern auch strafrechtlich verantwortlich machen.

3.3 Daraus ergibt sich, dass die nötige Zustimmung der anderen Stockwerkeigentümer rechtlich nicht erzwungen werden kann. Da sie gemäss den verbindlichen Feststellungen der Vorinstanz auch tatsächlich nicht eingeholt werden kann, steht der Beschwerdegegnerin ein unüberwindbares Leistungshindernis entgegen. Die Vorinstanz hat Art. 97 OR nicht verletzt, wenn sie von subjektiver Unmöglichkeit der Beseitigungsleistung ausgegangen ist.