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.

Erwägungen:
1. 1.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substantiiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss <ref-law> gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre; andernfalls kann ein Sachverhalt, der vom im angefochtenen Entscheid festgestellten abweicht, nicht berücksichtigt werden. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3, 462 E. 2.4).
1.2 Die Beschwerdeführer weichen in ihren Vorbringen über weite Strecken vom festgestellten Sachverhalt ab und erweitern diesen, ohne substantiierte Sachverhaltsrügen zu erheben. So beispielsweise wenn sie ausführen, dass der im Februar 2002 erfolgte Rückschnitt die Dienstbarkeit 1998 verletzt und alle Stockwerkeigentümer von dieser angeblichen Verletzung Kenntnis gehabt hätten. Mit ihrem pauschalen Vorbringen, dass die Streitsache zur Sachverhaltsergänzung an die Vorinstanz zurückzuweisen sei, falls nach Auffassung des Bundesgerichts einzelne von ihnen aufgeführte Sachverhaltselemente von der Vorinstanz nicht rechtsgenüglich festgestellt seien, vermögen sie den Begründungsanforderungen an eine Sachverhaltsrüge nicht zu genügen.
Im vorliegenden Verfahren ist zudem zu beachten, dass gegen das angefochtene Urteil des Obergerichts des Kantons Zürich die kantonale Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich nach § 281 des Gesetzes über den Zivilprozess vom 13. Juni 1976 (ZPO/ZH) möglich gewesen wäre. Soweit das angefochtene Urteil vom Kassationsgericht hätte überprüft werden können, ist es daher nicht kantonal letztinstanzlich. Auf Rügen, wonach der angefochtene Entscheid auf einer Verletzung eines wesentlichen Verfahrensgrundsatzes, auf einer aktenwidrigen oder willkürlichen tatsächlichen Annahme oder auf einer Verletzung klaren materiellen Rechts beruhe (<ref-law>/ZH), könnte demzufolge bereits von vornherein mangels Letztinstanzlichkeit nicht eingetreten werden (vgl. <ref-law>; Urteil 4A_22/2008 vom 10. April 2008, E. 1).
1.3 Auf die Beschwerde ist demzufolge nicht einzutreten, soweit die Beschwerdeführer über den von der Vorinstanz festgestellten Sachverhalt hinausgehen, ohne rechtsgenügende Sachverhaltsrügen - soweit entsprechende Rügen im vorliegenden Verfahren überhaupt gehört werden könnten - zu erheben. Ferner ist der generelle Verweis der Beschwerdeführer auf ihre Ausführungen in sämtlichen bisherigen Eingaben im kantonalen Verfahren unbeachtlich, hat doch die Begründung der Beschwerde in der Eingabe selbst enthalten zu sein (vgl. <ref-ruling> E. 2; <ref-ruling> E. 4a S. 30).
2. Die Vorinstanz kam in Gutheissung der Widerklage zum Schluss, dass der Grundbucheintrag der Dienstbarkeit 2002 ungerechtfertigt und daher zu löschen sei, da diesem mit dem Dienstbarkeitsvertrag vom 4. Juni 2002 ein unverbindliches Rechtsgeschäft zugrunde liege. Die V._ AG sei nicht bevollmächtigt gewesen, für die Beschwerdegegnerin den Dienstbarkeitsvertrag vom 4. Juni 2002 mit den Beschwerdeführern abzuschliessen. Zudem liege kein Fall des Gutglaubensschutzes vor.
3. Zunächst ist streitig, ob die als Stellvertreterin im Namen der Beschwerdegegnerin handelnde V._ AG durch den Willen der Vertretenen, d.h. der einzelnen Stockwerkeigentümer, zum Abschluss des Dienstbarkeitsvertrags vom 4. Juni 2002 genügend ermächtigt gewesen ist.
3.1 Unbestritten ist, dass die V._ AG aufgrund der Bevollmächtigung in den Kaufverträgen bestehende Dienstbarkeiten löschen, ändern oder weitere begründen durfte, allerdings nur insoweit, als sich dies "für die Überbauung aufgrund gesetzlicher Bestimmungen (Baubewilligung) oder rechtlicher Absicherung als notwendig erweist." Dass die Begründung der Dienstbarkeit 2002 aufgrund gesetzlicher Bestimmungen notwendig sei, wird nicht behauptet. Hingegen stellen sich die Beschwerdeführer auf den Standpunkt, die Begründung der Dienstbarkeit 2002 habe sich für die Überbauung aufgrund rechtlicher Absicherung als notwendig erwiesen. Indem die Vorinstanz dies verneinte, habe sie die der V._ AG in den einzelnen Kaufverträgen erteilte Vollmacht nicht richtig ausgelegt und sowohl die Auslegungsgrundsätze (<ref-law>) als auch das Vertrauensprinzip (<ref-law>) verletzt.
3.2 Der Umfang der Vollmacht beurteilt sich nach dem Inhalt der Bevollmächtigung (<ref-law>). Sofern nicht feststeht, dass der Vertreter den Vertretenen tatsächlich richtig verstanden hat, ist die Bevollmächtigung nach dem Vertrauensprinzip auszulegen (vgl. <ref-ruling> E. 6a S. 482; Gauch/Schluep/Schmid/Rey, Schweizerisches Obligationenrecht, Allgemeiner Teil, Band I, 8. Aufl., Zürich 2003, Rz. 1355; Watter/Schneller, Basler Kommentar, N. 17 zu <ref-law>; Zäch, Berner Kommentar, N. 114 zu <ref-law>). Massgeblich ist mithin, wie der Bevollmächtigte die Erklärung des Vollmachtgebers nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen nach Treu und Glauben verstehen durfte und musste (vgl. <ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 4 S. 28, 268 E. 2.3.2 S. 274 f., 626 E. 3.1 S. 632; <ref-ruling> E. 2.4, je mit Hinweisen). Wesentliche Gesichtspunkte sind dabei unter anderem der Zweck der Vollmacht, das Grundverhältnis und namentlich die Interessen des Vollmachtgebers (Urteil 4C.22/1999 vom 1. Juni 1999, E. 4b/aa). Diese objektivierte Auslegung der Bevollmächtigung als Willenserklärung überprüft das Bundesgericht als Rechtsfrage, wobei es an die Feststellungen des kantonalen Richters über die äusseren Umstände sowie das Wissen und Wollen der Beteiligten grundsätzlich gebunden ist (vgl. <ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 4 S. 28, 268 E. 2.3.2 S. 274 f., 626 E. 3.1 S. 632; <ref-ruling> E. 2.4, je mit Hinweisen). Ein klarer Wortlaut hat bei der Auslegung nach dem Vertrauensprinzip Vorrang vor weiteren Auslegungsmitteln. Selbst wenn der Wortlaut auf den ersten Blick klar erscheint, darf es bei einer reinen Wortauslegung nicht sein Bewenden haben, wenn sich aus den weiteren Umständen ergibt, dass der Wortlaut nicht genau den Sinn der Willenserklärung wiedergibt (vgl. <ref-law>; <ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 3.1 S. 286 f.; <ref-ruling> E. 2.4.1, je mit Hinweisen). Vom klaren Wortlaut ist jedoch nicht abzuweichen, wenn keine ernsthaften Zweifel daran bestehen, dass er dem Willen der Parteien entspricht (<ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 3.2 S. 425, je mit Hinweisen).
3.3 Vorliegend von Bedeutung ist somit, ob die V._ AG, resp. der für diese handelnde S._, die Vollmachtsklausel in den Kaufverträgen nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen dahingehend verstehen durfte und musste, dass die V._ AG zum Abschluss des Dienstbarkeitsvertrags vom 4. Juni 2002 bevollmächtigt sei.
Die Vorinstanz verwies zum Umfang der Vollmachtsklausel zunächst vollumfänglich auf die entsprechenden erstinstanzlichen Ausführungen. Das Bezirksgericht erwog insbesondere, aufgrund der Kaufverträge habe die V._ AG nur über eine sachlich beschränkte Vollmacht verfügt, wobei sich der Umfang der Bevollmächtigung auf für die Überbauung rechtlich notwendige Massnahmen beschränkt habe. Dass die zur Diskussion stehende Dienstbarkeit keine solche Massnahme darstelle, sei zu Recht unbestritten. Insbesondere begründe auch die Vereinbarung vom 14. Februar 2002 keine rechtliche Notwendigkeit für die Stockwerkeigentümer. Diese Vereinbarung habe der Architekt T._ ausdrücklich im Namen der V._ AG, die damals noch Eigentümerin der Liegenschaft Kat. Nr. 1 gewesen sei, unterzeichnet. Somit sei die V._ AG die alleine sie treffende obligatorische Verpflichtung eingegangen, einen Dienstbarkeitsvertrag mit einem bestimmten Inhalt abzuschliessen. Die Beschwerdeführer würden zudem implizit davon ausgehen, dass auch Änderungen, die nur im Interesse der Stockwerkeigentümer seien, durch die Vollmacht gedeckt wären. Dieser Ansicht sei aber auch dann nicht zu folgen, wenn man zwischen der Vollmachtsbestimmung und Ziff. 13 der Kaufverträge, worin der V._ AG als Totalunternehmerin das Recht eingeräumt werde, an den Ausführungsplänen "kleine Änderungen sowie unbedeutende Abweichungen" vorzunehmen, sofern sie sich überdies als "notwendig erweisen und zweckmässig sind", einen systematischen Zusammenhang sehen und deshalb die eine Klausel im Lichte der anderen auslegen wolle. Selbst wenn man der Auffassung der Beschwerdeführer folgen würde, wäre zudem nur die Begründung einer neuen Dienstbarkeit erfasst, die im eindeutigen Interesse aller Stockwerkeigentümer liegen würde. Ausgehend vom Wortlaut der Vollmachtserklärung bildeten die Bedürfnisse der Überbauung und nicht diejenige einzelner Stockwerkeinheiten den Massstab für den sachlichen Umfang der Vollmacht, was angesichts des Umstandes, dass eine Dienstbarkeit zu Lasten der gemeinschaftlichen Liegenschaft das Vermögen aller Stockwerkeigentümer in gleicher Weise belaste, auch die einzige sachkonforme Lösung darstelle. Die Verwendung des Wortes "notwendig" könne zudem nur so vernünftig interpretiert werden, dass dieses gemeinsame Interesse der Stockwerkeigentümer ein eindeutiges sein müsse. Das sei vorliegend nicht der Fall. Die Beschwerdeführer würden selber davon ausgehen, dass mit dem Dienstbarkeitsvertrag vom 4. Juni 2002 ein Ausgleich der Interessen der beteiligten Grundeigentümer erreicht worden sei. Der Architekt T._ habe ein Zurückschneiden der Hainbuche erbeten. Die Beschwerdeführer ihrerseits hätten im Gegenzug verlangt, dass eine Minimalhöhe eingehalten werde und die Bepflanzung so dicht sein müsse, dass die Sicht von ihrer Parzelle auf das Gebäude B._strasse 29 im Sommer vollständig abgedeckt werde. Beruhe aber eine Vereinbarung auf Geben und Nehmen und der Entscheid darüber, ob sie akzeptiert werden solle, damit auf dem Abwägen von Vor- und Nachteilen, könne sich höchstens die Frage stellen, ob die Vereinbarung unter Berücksichtigung aller Umstände als wünschbar erscheine oder nicht. Dass sie objektiv eindeutig im Interesse einer Personengruppe liege, sei dagegen ausgeschlossen. Vorliegend gelte dies umso mehr, als die bestehende Dienstbarkeit eine Pflicht der Beschwerdegegnerin zum Ersatz abgegangener Pflanzen durch ähnliche Bäume und Sträucher in der im Servitutsplan vorgeschriebenen Minimalhöhe vorsehe, was gegenüber der ursprünglichen Dienstbarkeit zu höheren Kosten für die Beschwerdegegnerin führen könnte. Demzufolge reiche die mit Abschluss der Kaufverträge schriftlich erklärte Vollmacht zur Begründung der Dienstbarkeit 2002 zulasten der Stockwerkeigentümer nicht aus. Weder sei die Begründung dieser Dienstbarkeit rechtlich zwingend noch eindeutig im Interesse aller Stockwerkeigentümer.
Die Vorinstanz fügte den Erwägungen des Bezirksgerichts ergänzend hinzu, es sei nicht nachvollziehbar, inwiefern die Überbauung als solche durch die Dienstbarkeit 2002 hätte abgesichert werden sollen bzw. inwiefern für die Überbauung ohne eine solche Dienstbarkeit eine Unsicherheit oder Gefährdung bestanden hätte. Die Notwendigkeit zur rechtlichen Absicherung der Überbauung könne auch nicht damit begründet werden, dass am 20. und 22. Februar 2002 unmittelbar nach der Unterzeichnung der Vereinbarung vom 14. Februar 2002 die gemäss der Dienstbarkeit 1998 geschützte Bepflanzung zurückgeschnitten und ausgelichtet worden sei. Allenfalls hätte der vor der Eigentumsübertragung erfolgte Rückschnitt finanzielle Folgen für die Beschwerdegegnerin nach sich gezogen, wobei offen bleiben könne, inwiefern diese allenfalls auf die Verkäuferin der Eigentumswohnungen oder andere für den vorzeitigen Rückschnitt verantwortliche Personen hätte überwälzt werden können. Dies hätte jedoch keineswegs die Überbauung als solche in Frage gestellt. Es wäre zu deren rechtlichen Absicherung nicht notwendig gewesen, die Dienstbarkeit 2002 zu begründen. Weder die Errichtung bzw. Fertigstellung noch der Weiterbestand bzw. die weitere Nutzung der Überbauung der Beschwerdegegnerin sei von dieser Dienstbarkeit abgehangen.
3.4 Die Beschwerdeführer bringen betreffend die Beurteilung des Umfangs der Vollmacht mehrere Rügen vor.
3.4.1 Der Vorwurf der Beschwerdeführer, wonach die Auslegung der Vollmachtsklausel beim Wortlaut stehen bleibe, wortklauberisch sei und sich nicht um den Sinn schere, ist unbegründet. Die Vorinstanz beschränkte sich nicht auf eine blosse Wortauslegung. So prüfte namentlich das Bezirksgericht - auf dessen Erwägungen die Vorinstanz verwies - unter Berücksichtigung der Vertragsziffer 13, ob die Vollmachtsklausel auch dahingehend hätte verstanden werden dürfen, dass nur im Interesse der Stockwerkeigentümer liegende Änderungen von der Vollmacht gedeckt seien.
3.4.2 Die Beschwerdeführer bringen mit Blick auf die Vollmachtsklausel insbesondere vor, eine rechtliche Absicherung könne notwendig sein, wenn - wie dies vorliegend aufgrund des am 20. und 22. Februar 2002 erfolgten Rückschnitts der Fall sei - eine nachbarrechtliche Auseinandersetzung, in welche die Überbauung involviert sei, zum Erhalt des Rechtsfriedens der Klärung bedürfe. Es sei im Interesse aller Stockwerkeigentümer gewesen, einem allfälligen Rechtsstreit mit Kostenfolgen zuvorzukommen. Die V._ AG hätte somit Massnahmen treffen müssen, die sich zur rechtlichen Absicherung als notwendig erwiesen.
Soweit die Beschwerdeführer mit dem im Februar 2002 erfolgten Rückschnitt argumentieren, verkennen sie, dass die Vorinstanz keine tatsächlichen Feststellungen bezüglich des Umfangs des Rückschnitts traf und insbesondere nicht feststellte, ob durch diesen Rückschnitt die Dienstbarkeit 1998 verletzt wurde. Dass der Beschwerdegegnerin eine nachbarrechtliche Auseinandersetzung gedroht hätte, ist ebenso wenig festgestellt. Zudem hat die Vorinstanz zutreffend ausgeführt, dass die Begründung der Dienstbarkeit 2002 zur rechtlichen Absicherung der Überbauung nicht notwendig gewesen sei, selbst wenn es zu einem Prozess gekommen wäre. Denn dieser hätte lediglich finanzielle Folgen nach sich gezogen, die allenfalls auf die für den Rückschnitt verantwortliche Person hätten überwälzt werden können.
3.4.3 Die Beschwerdeführer bringen mit Verweis auf Zäch vor, in der Vollmacht eingeschlossen seien insbesondere Geschäfte, die eine notwendige Voraussetzung für die vom Vertreter durchzuführende Handlung seien. Die Änderung der eingetragenen Dienstbarkeit sei eine notwendige Voraussetzung für die vertragskonforme Erfüllung durch die Bauherrschaft, da die im Verkaufsprospekt beschriebene Bepflanzung nicht der geltenden Dienstbarkeit 1998 entspreche. Zum einen erweitern sie auch hier wieder den vorinstanzlich festgestellten Sachverhalt, ohne rechtsgenügliche Sachverhaltsrügen zu erheben. Es wurde nämlich weder festgestellt, welche Bepflanzung nach Verkaufsprospekt geschuldet sei, noch ob diese der Dienstbarkeit 1998 entsprochen hätte. Zum andern verkennen die Beschwerdeführer, dass nach Zäch mit "vom Vertreter durchzuführende Handlungen" nur Handlungen gemeint sind, für die eine Bevollmächtigung vorliegt. So führt er an besagter Stelle aus, Vollmachtsformulare seien so auszulegen, dass nicht nur die jeweils konkret angegebenen Geschäfte für den Vertretenen abgeschlossen werden können, sondern andere Geschäfte eingeschlossen seien, wenn sie als "das Mindere" erscheinen würden. In der Vollmacht eingeschlossen seien insbesondere Geschäfte, die notwendige Voraussetzung für die vom Vertreter durchzuführende Handlung seien: Wenn beispielsweise der Vertreter eine Spezialvollmacht zur Errichtung der Hypothek besitze, die Hypothek aber erst nach Abschluss eines Teilungsvertrags errichtet werden könne, so sei er auch zum Abschluss des Teilungsvertrags berechtigt (Zäch, a.a.O., N. 116 zu <ref-law>). Vorliegend ist unbestritten, dass der V._ AG keine Vollmacht für alle zur vertragskonformen Erfüllung notwendigen Handlungen vorgelegen hat.
3.4.4 Die Rüge, wenn selbst eine Neubegründung einer Dienstbarkeit durch die Vollmacht gedeckt gewesen sei, müsse die Vollmacht umso mehr für eine blosse Änderung der Dienstbarkeit gelten, geht an der Sache vorbei. Dass aufgrund der Bevollmächtigung Dienstbarkeiten sowohl neu begründet als auch bloss geändert werden dürfen, ist unbestritten. Die Beschwerdeführer verkennen, dass sich aber auch eine blosse Änderung der Dienstbarkeit für die Überbauung aufgrund rechtlicher Absicherung als notwendig erweisen muss, damit diese von der Vollmacht gedeckt ist.
3.4.5 Die Beschwerdeführer gehen auch mit dem Argument fehl, dass selbst bei der Annahme, dass nur für die Überbauung existentiell notwendige Massnahmen von der Vollmacht gedeckt wären, eine genügende Bevollmächtigung für den Dienstbarkeitsvertrag vorgelegen hätte, da eine Gartenanlage auch zu einer Überbauung gehöre. Es ist nicht ersichtlich und wird von den Beschwerdeführern nicht dargetan, inwiefern die Vorinstanz unter "Überbauung" nicht auch die Gartenanlage mitgemeint hätte.
3.4.6 Die Beschwerdeführer bringen schliesslich vor, die Formulierung der Vollmachtsklausel sei üblich und entspreche - wie das Bezirksgericht festgestellt habe - der Verkehrssitte. Dabei verkennen sie die entsprechende Erwägung. Es trifft zu, dass das Bezirksgericht ausführte, es sei "vom Wortlaut der üblichen der V._ AG erteilten Vollmacht auszugehen". Aus dem Kontext ergibt sich aber, dass "üblich" nicht im Sinne von "der Verkehrssitte entsprechend" zu verstehen ist, sondern im Sinne von der "üblichen" Vollmachtsklausel, wie sie in den einzelnen, verschiedenen zwischen der V._ AG und den Stockwerkeigentümern geschlossenen Kaufverträgen enthalten ist. Die Beschwerdeführer können demnach aus dem behaupteten Umstand, wonach die Vollmachtsklausel der Verkehrssitte entsprechen würde, nichts zu ihren Gunsten ableiten.
3.5 Zusammenfassend ist festzuhalten, dass die Vorinstanz nicht Bundesrecht verletzte, indem sie zum Schluss kam, der Abschluss des Dienstbarkeitsvertrags vom 4. Juni 2002 falle nicht unter den sachlichen Umfang der Vollmachtsklausel und die V._ AG verfüge daher zum Abschluss dieses Vertrags über keine entsprechende Vollmacht der Beschwerdegegnerin.
4. Gemäss <ref-law> tritt eine Vertretungswirkung grundsätzlich nur ein, wenn der Vertreter über eine entsprechende Vollmacht des Vertretenen verfügt. Fehlt es an einer Vollmacht, wird der Vertretene weder berechtigt noch verpflichtet, ausser bei nachträglicher Genehmigung durch den Vertretenen (<ref-law>) oder wenn der Dritte in berechtigtem gutem Glauben auf das Bestehen der Vollmacht vertraut hat (Art. 33 Abs. 3, Art. 34 Abs. 3 und Art. 37 OR; vgl. <ref-ruling> E. 3.1; <ref-ruling> E. 2; Urteil 4C.12/2002 vom 14. Mai 2002, E. 3.1). Wie sich vorhergehend gezeigt hat, war die V._ AG aufgrund der in den Kaufverträgen enthaltenen Vollmachtsklausel nicht bevollmächtigt, den Dienstbarkeitsvertrag vom 4. Juni 2002 im Namen der Beschwerdegegnerin abzuschliessen. Die Beschwerdegegnerin wurde auch nicht durch den Dienstbarkeitsvertrag berechtigt oder verpflichtet, indem sie diesen nach <ref-law> genehmigt hätte. Zu prüfen bleibt somit, ob die Beschwerdegegnerin durch den Dienstbarkeitsvertrag dennoch gebunden ist, da die Beschwerdeführer in guten Treuen nach <ref-law> auf eine Vollmacht schliessen durften.
4.1 Wird die Ermächtigung vom Vollmachtgeber einem Dritten mitgeteilt, so beurteilt sich ihr Umfang diesem gegenüber nach Massgabe der erfolgten Kundgebung (<ref-law>). Durch diese Mitteilung wird jedoch keine Vollmacht begründet, sondern der Dritte lediglich über die bereits erteilte Vollmacht orientiert. Bedeutung kommt der Mitteilung dann zu, wenn sie mit der rechtsgeschäftlichen Ermächtigung inhaltlich nicht übereinstimmt (Urteil 4C.217/1994 vom 6. Januar 1995, E. 1a mit Hinweisen). Der gutgläubige Dritte wird in einem sol-chen Fall in dem Masse geschützt, wie ihm mitgeteilt wurde, auch wenn die Ermächtigung die vorgenommene Rechtshandlung nicht abdeckt (<ref-ruling> E. 3.2). Die Bindung des ungewollt Vertretenen beruht auf dem Vertrauensprinzip. Er ist nicht gebunden, weil er einen bestimmt gearteten Willen hat, sondern weil er ein Verhalten an den Tag legt, aus dem die Gegenseite in guten Treuen auf einen bestimmt gearteten Willen schliessen darf (BGE <ref-ruling> E. 2a; Urteil 4C.12/2002 vom 14. Mai 2002, E. 3.1). Zur Beurteilung des Inhalts der Vollmachtsmitteilung ist zu prüfen, wie der Dritte die Mitteilung über den Umfang der Vollmacht nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen in guten Treuen verstehen durfte und musste. Denn die Regeln über die Auslegung von Willenserklärungen sind sinngemäss auch auf eine rechtsgeschäftsähnliche Handlung wie die Mitteilung einer Ermächtigung anwendbar (<ref-ruling> E. 3.2.1 S. 518; Urteil 4C.217/1994 vom 6. Januar 1995, E. 1a, je mit Hinweisen). Zu berücksichtigen ist in diesem Zusammenhang wiederum, dass das Bundesgericht an die Feststellungen der Vorinstanz über die Umstände gebunden ist und dagegen als Rechtsfrage frei überprüft, wie die Mitteilung in guten Treuen verstanden werden durfte und musste (Urteil 4C.217/1994 vom 6. Januar 1995, E. 1a; vgl. auch <ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 4 S. 28, 268 E. 2.3.2 S. 274 f., 626 E. 3.1 S. 632; <ref-ruling> E. 2.4, je mit Hinweisen).
Der Gutglaubensschutz nach <ref-law> setzt insbesondere voraus, dass der Vertretene gegenüber dem Dritten die Ermächtigung mitgeteilt hat. Dies ist mittels einer Vollmachtsurkunde möglich, die der Vertreter dem Dritten übergibt (<ref-ruling> E. 3.2 und E. 3.2.1; <ref-ruling> E. 1 S. 42). Die Kundgabe der Ermächtigung kann auch erst anlässlich der öffentlichen Beurkundung erfolgen, indem der Vertreter dem Notar und Dritten die Vollmachtsurkunde vorweist (BGE 77 II 138 E. 2 S. 141 f.).
4.2 Vorliegend erfolgte die Mitteilung der in den Kaufverträgen enthaltenen Vollmachtsklausel gegenüber den Beschwerdeführern anlässlich der öffentlichen Beurkundung. Um den Umfang dieser mitgeteilten Vollmacht zu eruieren, ist somit danach zu fragen, wie die Beschwerdeführer diese Mitteilung nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen in guten Treuen verstehen durften und mussten. Die Beschwerdeführer machen nicht geltend und es ist nicht ersichtlich, dass der für die V._ AG handelnde S._ beim Notar eine Vollmacht, die vom Wortlaut der in den Kaufverträgen enthaltenen Vollmachtsklausel abweichen würde, vorgelegt hätte. Ebenso ist nicht ersichtlich und wird von den Beschwerdeführern auch nicht behauptet, dass die Beschwerdegegnerin den Beschwerdeführern auf eine andere Art und Weise eine im Wortlaut weitergehende Vollmacht mitgeteilt hätte. Zu prüfen ist demzufolge vorliegend, wie die Beschwerdeführer die in den Kaufverträgen statuierte Vollmachtsklausel nach dem Vertrauensprinzip verstehen durften und mussten. Dabei ist zu berücksichtigen, dass es sich beim Beschwerdeführer um eine rechtskundige Person handelt (Dr. iur., Rechtsanwalt).
4.3 Die Vorinstanz hat im Ergebnis nicht Bundesrecht verletzt, indem sie keine Vertretungswirkung aufgrund des Gutglaubensschutzes bejahte. Denn es ist nicht ersichtlich, dass die Beschwerdeführer die Vollmachtsklausel nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen in guten Treuen dahingehend verstehen durften und mussten, dass sich die Begründung der Dienstbarkeit 2002 für die Überbauung aufgrund rechtlicher Absicherung als notwendig erwiesen hätte und somit die V._ AG den entsprechenden Dienstbarkeitsvertrag vom 4. Juni 2002 hätte abschliessen dürfen.
Die Beschwerdeführer erweitern den von der Vorinstanz festgestellten Sachverhalt in unzulässiger Weise, wenn sie vorbringen, sie hätten vom Wunsch der neuen Eigentümer gewusst, die geschützte Bepflanzung zu ändern, sowie die Dienstbarkeit von 2002 hätte eine deutliche Verbesserung für die Stockwerkeigentümer dargestellt und die bestehende Dienstbarkeit 1998 wäre durch den Rückschnitt verletzt worden. Da die Beschwerdeführer bezüglich dieser Sachverhaltselemente keine substantiierten Sachverhaltsrügen erheben, kann auf ihre entsprechenden Ausführungen nicht eingetreten werden (vgl. Erwägung 1). Ebenso sind sie mit der Darlegung ihrer eigenen Sicht der Dinge nicht zu hören, wenn sie - wiederum ohne rechtsgenügliche Sachverhaltsrügen vorzutragen - geltend machen, die Beschwerdegegnerin habe den Verkaufsprospekt gekannt, der nicht mit der Dienstbarkeit 1998 korrespondiert habe, und mit dem Abschluss der Vereinbarung vom 14. Februar 2002 bzw. des Dienstbarkeitsvertrags vom 4. Juni 2002 sei keine Entschädigung verlangt worden (vgl. Erwägung 1).
Sowohl die Vorbringen der Beschwerdeführer, die Dienstbarkeit 2002 unterscheide sich nur geringfügig von der Dienstbarkeit 1998 und sei nicht neu, als auch das Argument, sie hätten mit dem Dienstbarkeitsvertrag vom 4. Juni 2002 auf ihre ursprüngliche Dienstbarkeit 1998 verzichtet, um die neue Dienstbarkeit im Grundbuch einzutragen, erweisen sich als unbehelflich. Es ist nicht nachvollziehbar, inwiefern die Beschwerdeführer durch die Berücksichtigung dieser Umstände hätten davon ausgehen dürfen, dass sich die Begründung der Dienstbarkeit 2002 für die Überbauung aufgrund rechtlicher Absicherung als notwendig erweise und die V._ AG somit gehörig bevollmächtigt sei. Schliesslich vermögen die Beschwerdeführer auch nichts zu ihren Gunsten aus dem Umstand abzuleiten, dass der Notar anlässlich der öffentlichen Beurkundung von einer ausreichenden Vollmacht ausgegangen ist.
5. Die Beschwerde ist demzufolge abzuweisen. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
2. Die Gerichtskosten von Fr. 5'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 6'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Obergericht des Kantons Zürich, II. Zivilkammer, und dem Kassationsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 25. September 2008
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Raselli Sommer