Sachverhalt: A. C._ ist Eigentümerin der Parzelle Nr. 276 im Dorfkern von Bever. Der östliche Teil der Liegenschaft ist mit einem Wohnhaus überbaut, auf dem westlichen Teil befindet sich ein Innenhof, der durch einen Holzzaun mit Einfahrtstor nach Süden gegen die Via Chà Suot abgegrenzt ist. Im Norden grenzt die Parzelle Nr. 276 an die Nr. 275 von A._ und B._. Diese ist mit einem Wohnhaus überbaut, wobei der östliche Teil der Südfassade mit dem Wohnhaus auf der Parzelle Nr. 276 zusammengebaut ist, während der westliche Teil der Südfassade den (nördlichen) Abschluss des Innenhofs der Parzelle Nr. 276 bildet. Die Parzelle Nr. 275 verfügt über einen Zugang über diesen Innenhof zur Via Chà Suot; dieser Teil der Parzelle Nr. 276 ist mit den entsprechenden Dienstbarkeiten - dem "unbeschränkten Fuss- und Fahrwegrecht sowie dem Recht des Aufstellens von Fahrzeugen und Handwagen aller Art" sowie dem "Recht, sich auf dem ganzen Areal der belasteten Parzelle aufzuhalten" - zugunsten der Parzelle Nr. 275 belastet. Am 4. April 2008 reichte C._ ein Baugesuch ein für die Verschiebung des bestehenden Einfahrtstores in den Innenhof von der Mitte an die Westgrenze der Liegenschaft. A._ und B._ erhoben Einsprache mit dem Antrag, das Baugesuch abzulehnen. Nach den von der Gemeinde eingeholten Erklärungen der Gesuchstellerin sollte mit der Verschiebung des Tores an den Parzellenrand eine rationellere Nutzung des Innenhofs (Zufahrt, Parkierung) unter Wahrung der privatrechtlichen Dienstbarkeitsvorgaben sowie die Schaffung eines zusätzlichen Aussenparkplatzes zwischen Zaun und Strasse erreicht werden. Nachdem C._ noch einen Situationsplan mit einer möglichen Parkordnung eingereicht hatte, genehmigte die Gemeinde Bever das Baugesuch und wies die Einsprache ab. A._ und B._ fochten die Baubewilligung beim Verwaltungsgericht des Kantons Graubünden an, welches die Beschwerde am 17. Februar 2009 abwies. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen A._ und B._, das verwaltungsgerichtliche Urteil sowie Ziff. III 1.-3. des Einsprache- und Baubewilligungsentscheids der Gemeinde Bever vom 21. Mai 2008 aufzuheben oder eventuell die Sache an die Gemeinde Bever zur Neubeurteilung oder subeventuell an das Verwaltungsgericht zur Beweisergänzung und Neubeurteilung zurückzuweisen. Die Sache sei dem Verwaltungsgericht zur Neubeurteilung der Kosten und Entschädigungsregelung zurückzuweisen. In verfahrensrechtlicher Hinsicht beantragen die Beschwerdeführer, der Beschwerde aufschiebende Wirkung zuzuerkennen und der Beschwerdegegnerin zu verbieten, das umstrittene Bauvorhaben zu realisieren. Ausserdem ersuchen sie, einen Augenschein durchzuführen. C. Mit Verfügung vom 13. Juli 2009 erkannte der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung zu. D. Die Gemeinde Bever verzichtet auf Vernehmlassung. Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen. C._ beantragt, auf die Beschwerde nicht einzutreten oder sie eventuell abzuweisen. A._ und B._ halten in der Replik an der Beschwerde fest. Die Gemeinde Bever teilt mit, dass A._ und B._ die Liegenschaft Nr. 275 per 1. Oktober 2009 an D._ verkauft haben; im Übrigen verzichtet sie auf Replik. C._ hält in der Duplik an ihrem Standpunkt fest. A._ und B._ bestätigen, die Liegenschaft Nr. 275 an D._ verkauft zu haben, und erklären, an der Beschwerde festzuhalten und den Streit in Prozessstandsschaft für die Erwerberin, welche ihr Interesse an der Gutheissung der Beschwerde erklärt habe, weiterzuführen. 