Citation: 1C_412/2016 E. 4

Nach dem Gesagten ist die Beschwerde teilweise gutzuheissen, soweit darauf einzutreten ist. Der angefochtene Entscheid ist aufzuheben und die Angelegenheit an das Verwaltungsgericht zurückzuweisen, damit dieses die Begründetheit des Vorbringens prüft, wonach der Vertrauensschutz der Wiederherstellung des rechtmässigen Zustands nicht entgegenstehe. Im Übrigen ist die Beschwerde abzuweisen. Bei diesem Verfahrensausgang obsiegen die Beschwerdeführer im Wesentlichen, weshalb die private Beschwerdegegnerin kostenpflichtig würde (Art. 66 Abs. 1 BGG) und den anwaltlich vertretenen Beschwerdeführern eine Parteientschädigung auszurichten hätte (Art. 68 Abs. 1 und 2 BGG). Unnötige Kosten hat indessen zu bezahlen, wer sie verursacht (Art. 66 Abs. 3 und Art. 68 Abs. 4 BGG). Vorliegend hat das Verwaltungsgericht gegen das Verbot der formellen Rechtsverweigerung und den Anspruch auf rechtliches Gehör verstossen. Es rechtfertigt sich daher, auf die Erhebung von Kosten zu verzichten und den Kanton Zürich zu verpflichten, den Beschwerdeführern für das bundesgerichtliche Verfahren eine angemessene Entschädigung auszurichten.