Sachverhalt: 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 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.--, ev. 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 (Ziff. 1 bis 3) aufzuheben und die Klage abzuweisen. B.c Mit Urteil vom 12. Februar 2008 (den Parteien schriftlich mitgeteilt am 1. Juli 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 (Ziff. 1, 3, 5 und 6) 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. 