Sachverhalt: A. A.a X._ und Y._ (Beschwerdeführer) bewohnen an der B._strasse 25 in C._ ein freistehendes Einfamilienhaus. Dieses befindet sich auf dem Grundstück Kat. Nr. 2, an dem sie Miteigentum haben. Am 14. Dezember 1998 schlossen die Beschwerdeführer mit W._, Eigentümerin des unmittelbaren Nachbargrundstücks Kat. Nr. 3 (B._strasse 27), und dem früheren Eigentümer des Grundstücks Kat. Nr. 1 (früher Kat. Nr. 4; B._strasse 29/31) einen Dienstbarkeitsvertrag betreffend Pflanzbeschränkung zu Gunsten des Grundstücks der Beschwerdeführer Kat. Nr. 2 und zu Lasten der Grundstücke Kat. Nr. 3 und Kat. Nr. 1. Gegenstand dieser Dienstbarkeit (nachfolgend: Dienstbarkeit 1998) bildeten ca. acht Bäume und Sträucher, mit denen die Sicht vom Haus der Beschwerdeführer auf das Grundstück Kat. Nr. 1 abgedeckt werden sollte. Die im Grundbuch eingetragene entsprechende Servitut SP Nr. 6 lautete wie folgt: "Die jeweiligen Eigentümer der belasteten Grundstücke sind verpflichtet, gegenüber dem jeweiligen Eigentümer des berechtigten Grundstückes die im Vertragsplan ad acta bezeichneten und rot markierten Bäume und Sträucher mindestens in der heutigen Höhe stehen zu lassen. Abgehende Bäume oder Sträucher hat der jeweilige Eigentümer des Grundstückes B (Kat. Nr. 1) auf seine Kosten durch ähnliche Pflanzen zu ersetzen, die mit gleich hohem Wuchs, höchstens aber bis zur Höhenkote von 540.20 m.ü.M. gepflanzt werden müssen." A.b Nachdem die V._ AG das Grundstück Kat. Nr. 1 erworben hatte, liess sie darauf eine Überbauung mit zwei Gebäuden mit mehreren Eigentumswohnungen erstellen. Zwischen dem 22. Januar 2001 und dem 11. Februar 2002 verkaufte sie die einzelnen, zu diesem Zeitpunkt noch nicht fertig gestellten Wohnungen. Die Dienstbarkeit 1998 sowie die dazu gehörenden Vertragspläne waren Bestandteil der Kaufverträge. In den Kaufverträgen wurde zudem folgende Vollmacht vereinbart: "Die Käuferschaft bevollmächtigt die Verkäuferin [V._ AG], befristet bis ein Jahr nach der Eigentumsübertragung, bei den Kaufsobjekten und den Gemeinschaftsparzellen bestehende Anmerkungen und Dienstbarkeiten zu löschen, zu ändern oder weitere zu begründen, soweit sich dies für die Überbauung aufgrund gesetzlicher Bestimmungen (Baubewilligung) oder rechtlicher Absicherung als notwendig erweist." Die Eigentumsübertragung der fertig gestellten Wohnungen auf die einzelnen Stockwerkeigentümer fand zwischen dem 26. Februar 2002 und dem 8. Mai 2002 statt. A.c Mit Vereinbarung vom 14. Februar 2002 verpflichteten sich die Beschwerdeführer, W._ und die V._ AG den Dienstbarkeitsvertrag vom 14. Dezember 1998 bis spätestens am 28. März 2002 durch einen neuen, in der Vereinbarung genau umschriebenen Vertrag zu ersetzen. Die Bepflanzung wurde am 20. und 22. Februar 2002 zurückgeschnitten und ausgelichtet. Am 4. Juni 2002 schlossen die Beschwerdeführer, W._ und die V._ AG im Namen der Stockwerkeigentümergemeinschaft der Liegenschaft Kat. Nr. 1 (Beschwerdegegnerin) den gleichentags auf dem Notariat D._ öffentlich beurkundeten Dienstbarkeitsvertrag. Gestützt auf diesen Vertrag wurde im Grundbuch die Dienstbarkeit 1998 gelöscht und zu Gunsten der Liegenschaft der Beschwerdeführer Kat. Nr. 2 und zu Lasten der Liegenschaft Kat. Nr. 3 sowie der gemeinschaftlichen Liegenschaft der Beschwerdegegnerin Kat. Nr. 1 eine neue Dienstbarkeit SP 7 (nachfolgend: Dienstbarkeit 2002) mit folgendem Wortlaut eingetragen: "Die jeweiligen Eigentümer der belasteten Liegenschaften (Kat. Nr. 1, 3) sind verpflichtet, an der Grenze zwischen ihren Liegenschaften eine Bepflanzung gemäss Servitutsplan beizubehalten und zu unterhalten. Diese Bepflanzung hat so dicht zu sein, dass im Sommer die Sicht von der berechtigten Liegenschaft auf die Gebäude auf der Liegenschaft Kat. Nr. 1 und die B._strasse vollständig abgedeckt wird. Die im Servitutsplan eingezeichneten Mindesthöhen müssen bis spätestens zum 31. Mai 2003 eingehalten werden. Die Kosten für die Beibehaltung und den Unterhalt der vorerwähnten Bepflanzung gehen ausschliesslich zu Lasten der Eigentümer der Liegenschaft Kat. Nr. 1. Abgehende Pflanzen haben diese Eigentümer auf ihre Kosten durch ähnliche Pflanzen zu ersetzen, die mit gleichem Wuchs bis zu der im Servitutsplan vorgeschriebenen Minimalhöhe gepflanzt werden müssen." A.d U._, eine Stockwerkeigentümerin der Beschwerdegegnerin, liess am 23. September 2003 die geschützten Bäume und Sträucher teilweise entfernen. In welchem Umfang ist strittig. Die Beschwerdegegnerin liess im November 2003 die entfernten Pflanzen durch neue ersetzen. Diese Ersatzpflanzung entspricht nach Auffassung der Beschwerdeführer weder den Anforderungen der Dienstbarkeit 2002 noch derjenigen von 1998. B. B.a Die Beschwerdeführer reichten beim Bezirksgericht Meilen am 5. April 2004 gegen die Beschwerdegegnerin Klage ein mit folgendem Rechtsbegehren: "Die Beklagte [Beschwerdegegnerin] sei zu verpflichten, entlang der Grenze zwischen Kat. Nr. 1 und Kat. Nr. 3 in ca. 2 m Entfernung und bis auf die Höhe der bergseitigen Fassade des Gebäudes B._strasse 29 sechs Bäume mit einer Grösse von 9 m bis 10.5 m zu pflanzen und dabei den Bepflanzungsplan sowie die Zwecksetzung der Dienstbarkeit vom 4. Juni 2002 einzuhalten; im Falle der Nichterfüllung innert 6 Monaten nach Rechtskraft des Urteils seien die Kläger [Beschwerdeführer] zur Ersatzvornahme zu ermächtigen, und die Beklagte [Beschwerdegegnerin] sei zu verpflichten, einen Kostenvorschuss in der Höhe von Fr. 100'000.-- zu bezahlen." Die Beschwerdegegnerin erhob Widerklage mit dem Antrag, die Nichtigkeit der Dienstbarkeit 2002 festzustellen und das Grundbuchamt D._ anzuweisen, diese Dienstbarkeit im Grundbuch zu löschen. Das Bezirksgericht wies die Klage am 10. November 2006 ab (Ziff. 1). Es stellte in Gutheissung der Widerklage fest, dass die Dienstbarkeit 2002 nicht bestehe und wies das Grundbuchamt an, den ungerechtfertigten Eintrag im Grundbuch zu löschen (Ziff. 2). B.b Die Beschwerdeführer gelangten gegen das Urteil des Bezirksgerichts vom 10. November 2006 mit kantonaler Berufung an das Obergericht des Kantons Zürich. Sie begehrten, das angefochtene Urteil aufzuheben und die Widerklage abzuweisen. An ihrem vor dem Bezirksgericht gestellten Rechtsbegehren hielten sie nicht mehr vollumfänglich fest, sondern reduzierten es insoweit, als sie nur noch die Pflanzung von vier Bäumen und einen Kostenvorschuss für eine allfällige Ersatzvornahme von Fr. 60'000.-- forderten (Ziff. 1). Weiter beantragten sie, das Grundbuchamt anzuweisen, die Dienstbarkeit 1998 wieder im Grundbuch einzutragen für den Fall, dass der Grundbucheintrag der Dienstbarkeit 2002 infolge ungenügender Vollmacht wider Erwarten zu löschen wäre (Ziff. 2). Die Beschwerdegegnerin stellte den Antrag, es sei Vormerk zu nehmen, dass die Beschwerdeführer ihr ursprünglich gestelltes Rechtsbegehren reduziert hätten. Das noch verbleibende Rechtsbegehren sei abzuweisen und auf den Antrag betreffend Wiedereintragung der Dienstbarkeit 1998 sei nicht einzutreten. Das Obergericht merkte mit Beschluss vom 22. Januar 2008 vor, dass Ziff. 1 des Dispositivs des Urteils des Bezirksgerichts insofern in Rechtskraft erwachsen sei, als damit die Klage bezüglich der Verpflichtung der Beschwerdegegnerin zur Pflanzung von mehr als vier Bäumen und zur Leistung eines Kostenvorschusses von mehr als Fr. 60'000.-- für den Fall der Nichterfüllung abgewiesen werde. Es beschloss weiter, auf Ziff. 2 des Berufungsantrags der Beschwerdeführer nicht einzutreten. Mit Urteil vom selben Tag wies es die Klage ab, soweit sie noch zu beurteilen war, und stellte in Gutheissung der Widerklage fest, dass der Grundbucheintrag der Dienstbarkeit 2002 ungerechtfertigt sei. Demzufolge wies es das Grundbuchamt an, diesen Eintrag im Grundbuch zu löschen. C. Mit Beschwerde in Zivilsachen vom 27. Februar 2008 beantragen die Beschwerdeführer, das Urteil des Obergerichts vom 22. Januar 2008 aufzuheben. Die Beschwerdegegnerin sei zu verpflichten, "entlang der Grenze zwischen Kat. Nr. 1 und Kat. Nr. 3 in ca. 2 m Entfernung sowie zwischen der alten Hainbuche an der B._strasse und der 2003 gepflanzten Hainbuche östlich davon vier Bäume in der Höhe von 9 bis 10,5 m zu pflanzen und dabei den Bepflanzungsplan sowie die Zwecksetzung der Dienstbarkeit vom 4. Juni 2002 einzuhalten. Im Falle der Nichterfüllung innert 6 Monaten nach Rechtskraft des Urteils seien die Beschwerdeführer zur Ersatzvornahme zu ermächtigen, und die Beschwerdegegnerin sei zu verpflichten, einen Kostenvorschuss in der Höhe von Fr. 60'000.-- zu bezahlen." Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde und Bestätigung des angefochtenen Urteils. Das Obergericht verzichtet auf eine Vernehmlassung. Die Beschwerdeführer haben das Urteil des Obergerichts nicht mit kantonaler Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich weitergezogen. Hingegen haben sie gegen den Beschluss des Obergerichts vom 22. Januar 2008 Nichtigkeitsbeschwerde erhoben. Das Kassationsgericht verfügte am 17. März 2008, das Beschwerdeverfahren bis zum Entscheid des Bundesgerichts zu sistieren. 