Sachverhalt: A. Die Baukommission Uetikon am See erteilte X._ am 24. Januar 2011 die baurechtliche Bewilligung für die Erstellung von zwei Mehrfamilienhäusern auf dem Grundstück Kat.-Nr. 4756 an der Seestrasse 132 und 134 in Uetikon am See. Dieses war im 19. und frühen 20. Jahrhundert durch die Aufschüttung von Seegebiet gewonnen und im Konzessionsverfahren vergeben worden (sog. Landanlagegebiet). Gleichzeitig mit dem baurechtlichen Entscheid wurde die im koordinierten Verfahren ergangene raumplanungsrechtliche, konzessionsrechtliche und gewässerschutzrechtliche Bewilligung der Baudirektion Zürich vom 17. Januar 2011 eröffnet. B. Den dagegen erhobenen Rekurs des Schweizer Heimatschutzes und der Zürcherischen Vereinigung für Heimatschutz hiess das Baurekursgericht des Kantons Zürich am 23. August 2011 teilweise gut und hob die Verfügung der Baudirektion vom 17. Januar 2011 insoweit auf, als damit eine Ausnahmebewilligung für eine ostseitige Hecke und einen Zaun erteilt worden war. Im Übrigen wies es den Rekurs ab. Die Kosten des Rekursverfahrens von Fr. 15'250.-- (bestehend aus einer Gerichtsgebühr von Fr. 15'000.-- und Zustellkosten von Fr. 250.-) wurden den Rekurrierenden zu je 11/24 (unter solidarischer Haftung für 11/12) sowie der Baudirektion des Kantons Zürich und X._ zu je 1/24 auferlegt. Die Rekurrierenden wurden verpflichtet, X._ eine Umtriebsentschädigung von Fr. 2'900.-- zu bezahlen. C. Am 30. September 2011 erhoben der Schweizer Heimatschutz und die Zürcherische Vereinigung für Heimatschutz mit gemeinsamer Eingabe Beschwerde an das Verwaltungsgericht des Kantons Zürich. Am 2. Dezember 2011 zog X._ sein Baugesuch zurück und beantragte die Abschreibung des Beschwerdeverfahrens zufolge Gegenstandslosigkeit. Am 30. Mai 2012 schrieb das Verwaltungsgericht die Beschwerde in Bezug auf die Frage der Rechtmässigkeit der Baubewilligung als gegenstandslos geworden ab. Im Übrigen hiess es die Beschwerde gut und reduzierte die Gerichtsgebühr des Baurekursgerichts auf Fr. 10'000.--. Die Kosten des verwaltungsgerichtlichen Verfahrens wurden zu einem Drittel auf die Gerichtskasse genommen und zu zwei Dritteln X._ auferlegt. Dieser wurde verpflichtet, den Beschwerdeführern eine Parteientschädigung von je Fr. 750.-- zu bezahlen. Dem verwaltungsgerichtlichen Entscheid liegt eine Minderheitsbegründung bei, wonach der Rückzug des Baugesuchs als Anerkennung der Beschwerde zu werten sei und dem Beschwerdegegner daher auch die Kosten des Rekursverfahrens hätten auferlegt werden müssen. D. Gegen den verwaltungsgerichtlichen Entscheid haben der Schweizer Heimatschutz und die Zürcherische Vereinigung für Heimatschutz am 23. August 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben, soweit darin die Kosten- und Entschädigungsregelung des Baurekursgerichts zu ihren Lasten bestätigt worden sei. Die Sache sei zur Neuverlegung der Kosten im Sinne der Erwägungen an das Verwaltungsgericht, eventualiter an das Baurekursgericht, zurückzuweisen. Eventualiter möge das Bundesgericht den angefochtenen Entscheid in der Sache selbst ändern und dem Beschwerdegegner 23/24 der Kosten des Rekursverfahrens auferlegen und diesen verpflichten, ihnen eine Umtriebsentschädigung für das Rekursverfahren von je Fr. 1'750.-- (insgesamt Fr. 3'500.--) zu bezahlen. Subeventualiter sei die Sache an das Verwaltungsgericht zurückzuweisen, um die Gerichtsgebühr für das Rekursverfahren auf deutlich unter Fr. 10'000.-- zu reduzieren. E. Der Beschwerdegegner und das Verwaltungsgericht beantragen, die Beschwerde sei abzuweisen. Die Baudirektion hat auf eine Vernehmlassung verzichtet. Das Baurekursgericht verzichtet auf eine Stellungnahme zum Hauptantrag und beantragt sinngemäss die Abweisung des Eventualantrags auf Reduktion der Gerichtsgebühr für das Rekursverfahren.