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.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid in einer öffentlich-rechtlichen Angelegenheit (Art. 82 lit. a und Art. 86 Abs. 1 lit. d BGG).
1.1 Zwar haben die Beschwerdeführer vor Verwaltungsgericht obsiegt, d.h. ihre Beschwerde wurde gutgeheissen, soweit sie nicht als gegenstandslos abgeschrieben worden ist. Soweit sie jedoch geltend machen, ihnen seien zu Unrecht Kosten- und Entschädigungsfolgen für das Rekursverfahren auferlegt worden, sind sie zur Beschwerde legitimiert (<ref-law>), und zwar grundsätzlich unabhängig von ihrer Legitimation in der Sache. Insofern kann offenbleiben, ob und inwiefern sie sich auf das Verbandsbeschwerderecht nach Art. 12 des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451) berufen können.
1.2 Auf die Beschwerde ist daher grundsätzlich einzutreten. Die Frage, ob der Subeventualantrag auf Rückweisung der Sache zur Neufestsetzung der Gerichtsgebühr des Baurekursgerichts auf "deutlich unter Fr. 10'000.--" zulässig ist, ist unten (E. 4) näher zu prüfen.
1.3 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht kann insbesondere die Verletzung von Bundesrecht gerügt werden (<ref-law>); dies prüft das Bundesgericht grundsätzlich von Amtes wegen (<ref-law>). Die Verletzung von Grundrechten (einschliesslich die willkürliche Anwendung von kantonalem Recht) wird vom Bundesgericht nur insoweit geprüft, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Für derartige Rügen gelten qualifizierte Begründungsanforderungen (<ref-ruling> E. 1.4.2 S. 254 mit Hinweisen).
2. Streitig ist in erster Linie die Kostenverteilung für das Verfahren vor dem Baurekursgericht (zur Höhe der Gerichtsgebühr vgl. unten E. 4).
2.1 Die Beschwerdeführer halten den Entscheid der Mehrheit des Verwaltungsgerichts für willkürlich; richtig sei die Minderheitsmeinung. Nach § 13 Abs. 2 Satz 1 des Zürcher Verwaltungsrechtspflegegesetzes vom 24. Mai 1959 (VRG) trage die unterliegende Partei die Gebühren und Kosten nach Massgabe ihres Unterliegens (Unterliegerprinzip). Nach herrschender Lehre und Rechtsprechung gelte u.a. als unterliegend, wer dafür sorge, dass ein Verfahren gegenstandslos werde (ALFRED KÖLZ/JÖRG BOSSHART/MARTIN RÖHL, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Aufl., Zürich 1999, N. 15 zu § 13 VRG); nur in den übrigen Fällen der Gegenstandslosigkeit, wenn keine Partei unterliege, seien die Kosten nach den Prozessaussichten vor Gegenstandslosigkeit zu verlegen (KÖLZ/BOSSHART/RÖHL, a.a.O., N. 19 zu § 13 VRG). Insbesondere gelte der Rückzug eines Baugesuchs als Anerkennung der dagegen erhobenen Rechtsmittel und führe zum Unterliegen der Bauherrschaft für das gesamte Verfahren.
2.2 Die Mehrheit des Verwaltungsgerichts ging dagegen davon aus, dass der Rückzug des Baugesuchs aufgrund der konkreten Umstände nicht als Anerkennung der Beschwerde bzw. des Rekurses zu werten sei und deshalb, für sich allein, keine Abänderung des vorinstanzlichen Kostenentscheids rechtfertige.
Der Beschwerdegegner weist auf die besonderen Umstände des vorliegenden Falles hin: Das streitbetroffene Grundstück werde entsprechend einer rechtskräftigen Baubewilligung aus dem Jahre 2008 überbaut. Das vor Baurekursgericht streitige Baugesuch habe gewisse geringfügige Modifikationen des Projekts bezweckt. Die Beschwerdeführer hätten somit ihr Ziel, die Überbauung des Grundstücks zu verhindern bzw. eine Antwort auf die strittigen Fragen des Konzessionslandes zu erhalten, gar nicht erreichen können.
2.3 Die Beschwerdeführer wenden dagegen ein, der Beschwerdegegner habe sein Baugesuch eingereicht, bevor er sich mit der Grundeigentümerin abschliessend über den Erwerb des Baugrundstücks geeinigt hatte. Er sei damit das Risiko eingegangen, dass die Verhandlungen scheitern könnten und er sein Baugesuch zurückziehen müsse. Es sei willkürlich, dieses Risiko den Beschwerdeführern aufzuerlegen, die gar keine Kenntnis von diesen Hintergründen gehabt hätten.
Die Mehrheit des Verwaltungsgerichts argumentiere völlig widersprüchlich, wenn sie die Kostenverteilung des Baurekursgerichts belasse, dem Beschwerdegegner aber die verwaltungsgerichtlichen Kosten auferlege, mit der Begründung, dass dieser die Gegenstandslosigkeit des Beschwerdeverfahrens mit dem Verzicht auf das angefochtene Bauvorhaben verursacht habe.
In diesem Zusammenhang sei schliesslich zu berücksichtigen, dass die Beschwerdeführer mit ihren Rechtsmitteln im öffentlichen Interesse einen Grundsatzentscheid über Inhalt und Tragweite des Eigentums an aufgeschüttetem Seegebiet und zur nachträglichen Befristung von zeitlich unbegrenzten Landanlagekonzessionen erreichen wollten.
Schliesslich liege auch eine Verletzung der "wohlfeilen Erledigung des Verfahrens" gemäss Art. 18 Abs. 1 der Verfassung des Kantons Zürich vom 27. Februar 2005 (KV/ZH) vor, wenn die Verbände (hohe) Kosten für ein Verfahren tragen müssten, das ohne ihr Zutun vorzeitig abgebrochen worden sei.
2.4 Wie sich aus den verwaltungsgerichtlichen Akten ergibt, hatte die Gemeinde Uetikon (mit Genehmigung der Baudirektion) bereits am 11. August 2008 der Y._ AG als Grundstückseigentümerin eine Bewilligung für ein Bauvorhaben auf der Parzelle Nr. 4756 erteilt. Diese Bewilligung ist rechtskräftig geworden. Am 3. September 2009 wurde die Baufreigabe erteilt. Anschliessend erfolgte der Abbruch des bestehenden Gebäudes Vers.-Nr. 457.
Der Beschwerdegegner steht seit Dezember 2009 in Verhandlungen mit der Y._ AG für den Kauf des Grundstücks. Er wollte gewisse Änderungen am Bauprojekt vornehmen, die aus Sicht der Gemeinde eine neue Ausschreibung erforderten. Er reichte deshalb ein neues Baugesuch ein, gegen das die Beschwerdeführer Rechtsmittel erhoben. Diesen ging es nicht um die Projektänderungen, sondern darum, die Überbauung des am Seeufer liegenden Grundstücks zu verhindern. Gleichzeitig wollten sie einen Entscheid zu der - ihres Erachtens gebotenen - nachträglichen Befristung von zeitlich unbegrenzt erteilten Landanlagekonzessionen erreichen.
Am 24. November 2011 bzw. 2. Dezember 2011 teilten die Y._ AG und der Beschwerdegegner mit, dass die Y._ AG ihr ursprüngliches Bauvorhaben weiterführen und das Baugesuch des Beschwerdegegners zurückgezogen werde.
2.5 Willkür liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder sogar vorzuziehen wäre. Das Bundesgericht weicht vom Entscheid der kantonalen Instanz nur ab, wenn dieser offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E 2.2.2 S. 318 f. mit Hinweisen).
Im vorliegenden Fall hatte der Rückzug des Baugesuchs zwar zur Folge, dass der Beschwerdegegner sein Bauvorhaben nicht mehr realisieren kann. Allerdings können auch die Beschwerdeführer ihr Ziel, die Überbauung des Grundstücks zu verhindern, nicht erreichen. Dieses wird vielmehr mit dem bereits rechtskräftig bewilligten Projekt der Y._ AG überbaut.
Unter diesen besonderen Umständen erscheint es zumindest nicht willkürlich davon auszugehen, dass weder die Beschwerdeführer noch der Beschwerdegegner obsiegen bzw. unterliegen. Dies hat zur Folge, dass das Verwaltungsgericht willkürfrei vom reinen Unterliegerprinzip abweichen und bei seiner Kostenregelung auch die Prozessaussichten berücksichtigen durfte. Dabei kam es bei summarischer Prüfung zum Ergebnis, dass das Baurekursgericht in der Sache richtig entschieden habe. In dieser Situation entschied es sich für eine nach Instanzen differenzierte Regelung: Für die erstinstanzlichen Kosten behielt es die Kostenverteilung des Baurekursgerichts bei, legte dagegen dem Beschwerdegegner die Kosten des nutzlos gewordenen zweitinstanzlichen Verfahrens auf. Diese differenzierte Lösung erscheint jedenfalls nicht offensichtlich unhaltbar und damit willkürlich.
2.6 Der Umstand, dass die Beschwerdeführer mit ihrer Verbandsbeschwerde ideelle Interessen vertraten, ist nicht bei der Kostenverteilung, sondern bei der Kostenbemessung zu berücksichtigen (vgl. unten E. 4). Gleiches gilt für die Garantie eines wohlfeilen Verfahrens gemäss Art. 18 Abs. 1 KV/ZH.
3. Die Beschwerdeführer rügen ferner, der angefochtene Entscheid sei nicht haltbar und somit willkürlich, soweit darin die Erfolgsaussichten der Beschwerde verneint würden.
3.1 Sie machen geltend, sie hätten im Rekursverfahren auch die Verletzung der am 1. Juni 2011 in Kraft getretenen Revision der Gewässerschutzverordnung vom 28. Oktober 1998 (GSchV; SR 814.201) gerügt. Das Baurekursgericht habe dazu lediglich erwogen, dass die Messweise des Mindestgewässerabstands bzw. die Abstände, welche die Bauten zum See einzuhalten hätten, bereits mit dem Gestaltungsplan rechtskräftig und bindend festgelegt worden seien, woran die neue Gewässerschutzgesetzgebung nichts zu ändern vermöge. Der Gestaltungsplan datiere jedoch vom 1. März 2007 und sei am 4. Juli 2007 von der Baudirektion genehmigt worden, lange vor dem Bekanntwerden und Inkrafttreten der neuen bundesrechtlichen Gewässerschutzbestimmungen. Darauf sei die Vorinstanz überhaupt nicht eingegangen. Dies sei willkürlich, hätte doch schon eine summarische Prüfung der Erwägungen des Baurekursgerichts ergeben müssen, dass der Rekursentscheid in diesem wichtigen Punkt nicht haltbar sei.
3.2 Das Baurekursgericht argumentierte jedoch nicht ausschliesslich mit der Bestandskraft des Gestaltungsplans. Vielmehr hielt es (in E. 5.3 S. 32) auch fest, dass die projektierten Mehrfamilienhäuser den künftig festzulegenden Gewässerraum nicht verletzten: Der Gebäudekomplex weise zum Seeufer einen Abstand von 27.5 m auf und liege somit weit ausserhalb des gemäss Übergangsbestimmungen zur Änderung der GSchV vom 4. Mai 2011 einzuhaltenden Gewässerraumes von 20 m. Die bestehende Seeufertreppe sei gemäss Art. 41c Abs. 2 GSchV in ihrem Bestand geschützt. Die Beschwerdeführer legen nicht dar, inwiefern diese Erwägung auf einer bei summarischer Betrachtung unhaltbaren Rechtsanwendung oder Sachverhaltsfeststellung beruht.
Ist somit auf die Rüge schon mangels genügender Begründung nicht einzutreten (<ref-law>), kann offen bleiben, ob und inwiefern die Beschwerdeführer zur (indirekten) Erhebung von Sachrügen legitimiert sind (vgl. oben, E. 1.1).
4. Die Beschwerdeführer machen schliesslich geltend, sie hätten schon vor Verwaltungsgericht eine Reduktion der Gerichtsgebühr des Baurekursgerichts auf deutlich unter Fr. 10'000.-- beantragt. Diesen Antrag habe das Verwaltungsgericht willkürlich dahingehend interpretiert, dass eine Reduktion auf Fr. 10'000.--, verlangt werde (E. 3.2 S. 7 f. des angefochtenen Entscheids). Es habe daher die Angemessenheit einer tieferen Gebühr gar nicht mehr überprüft, obwohl es selbst davon ausgegangen sei, dass "sich allenfalls eine noch stärkere Reduktion gerechtfertigt hätte" (E. 3.9.6 S. 16). Damit habe es eine willkürliche Ermessensunterschreitung und eine Rechtsverweigerung begangen.
Es sei überspitzt formalistisch und willkürlich, einen bezifferten Antrag zu verlangen, weil bei der Festsetzung einer Gerichtsgebühr ein weiter Ermessensspielraum bestehe und die konkret angemessene Gebühr von den Beschwerdeführern gar nicht bezifferbar sei. Eventualiter hätte das Verwaltungsgericht nach § 56 Abs. 1 VRG vorgehen und den Beschwerdeführern Frist setzen müssen, um einen eindeutig bezifferten Antrag zu stellen. Dagegen sei es willkürlich gewesen, den eindeutig formulierten Antrag der Beschwerdeführer entgegen seinem Wortlaut umzuinterpretieren.
4.1 Das Verwaltungsgericht hielt fest, dass Beschwerdeanträge, nach denen sich der Streitgegenstand bestimme, ziffernmässig zumindest bestimmbar sein müssten, sofern Geldbeträge streitig seien (KÖLZ/ BOSSHART/RÖHL, a.a.O., N. 3 zu § 54 VRG). Der Wortlaut des Eventualantrags der Beschwerdeführer genüge diesen Anforderungen nicht. Das Begehren sei indessen dahingehend auszulegen, dass eine Reduktion der Gerichtsgebühr auf Fr. 10'000.-- verlangt werde. Über diesen Antrag könne das Verwaltungsgericht nicht hinausgehen (E. 3.2 S. 7 f. des angefochtenen Entscheids).
4.2 Überspitzter Formalismus als besondere Form der Rechtsverweigerung (<ref-law>) liegt vor, wenn für ein Verfahren rigorose Formvorschriften aufgestellt werden, ohne dass die Strenge sachlich gerechtfertigt wäre, wenn die Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und damit dem Bürger den Rechtsweg in unzulässiger Weise versperrt (<ref-ruling> E. 2.1 S. 9 mit Hinweisen).
4.2.1 Nicht jede prozessuale Formstrenge stellt einen überspitzten Formalismus dar, sondern nur jene, die durch kein schutzwürdiges Interesse mehr gerechtfertigt ist und zum blossen Selbstzweck wird. Prozessuale Formen sind unerlässlich, um die ordnungsgemässe Abwicklung des Verfahrens sowie die Durchsetzung des materiellen Rechts zu gewährleisten. Eingaben an Behörden, vor allem Rechtsmittelschriften, haben daher im allgemeinen bestimmten formellen Anforderungen zu genügen: Es soll aus ihnen hervorgehen, dass und weshalb der Rechtsuchende einen Entscheid anficht und inwieweit dieser geändert oder aufgehoben werden soll (<ref-ruling> E. 2.4.2 S. 248 mit Hinweisen).
Nach ständiger Praxis ist es zulässig und nicht überspitzt formalistisch, die Bezifferung des Rechtsbegehrens zu verlangen, wenn Geldbeträge streitig sind (<ref-ruling> E. 6.1 S. 621 mit Hinweisen). Dies gilt auch bei der selbstständigen Anfechtung von Kostenentscheiden (vgl. Urteile des Bundesgerichts 4A_225/2011 vom 15. Juli 2011 E. 2.6.2; 5A_34/2009 vom 26. Mai 2009 E. 11.3, nicht publ. in <ref-ruling>; 4A_43/2008 vom 4. März 2008 E. 2.1, publ. in: Praxis 97/2008 Nr. 121 S. 756). Die Bezifferung dient der Festlegung des Streit- bzw. Beschwerdegegenstands und definiert gleichzeitig die Entscheidbefugnisse der Rechtsmittelinstanz, wenn diese reformatorisch entscheiden kann und an die Rechtsbegehren der Parteien gebunden ist.
Ausnahmsweise kann das Beharren auf einer Bezifferung bundesrechtswidrig sein, wenn der Kläger nicht in der Lage ist, die Höhe seines Anspruchs genau anzugeben oder diese Angabe unzumutbar erscheint (vgl. <ref-ruling> E. 4a S. 219 f. mit Hinweisen). Überdies steht die Rechtsfolge des Nichteintretens unter dem Vorbehalt des überspitzten Formalismus, d.h. auf ein formell mangelhaftes Rechtsbegehren ist ausnahmsweise einzutreten, wenn sich aus der Begründung, allenfalls in Verbindung mit dem angefochtenen Entscheid, ergibt, was verlangt wird bzw. welcher Geldbetrag zuzusprechen ist (<ref-ruling> E. 6.2 S. 621 f. mit Hinweisen).
4.2.2 Vorliegend hatten die Beschwerdeführer vor Verwaltungsgericht eine Herabsetzung der vorinstanzlichen Gerichtsgebühr von Fr. 15'000.-- durch das Verwaltungsgericht, d.h. einen reformatorischen Entscheid betreffend eines Geldbetrags, verlangt. Zwar stand dem Baurekursgericht bei der Festsetzung der Parteientschädigung ein grosser Ermessensspielraum zu; das Verwaltungsgericht konnte jedoch im Beschwerdeverfahren die Angemessenheit der Gebühr nicht frei überprüfen, sondern war auf eine Rechtskontrolle beschränkt. Die Beschwerdeführer hatten die Verletzung des Willkürverbots und des Anspruchs auf ein "wohlfeiles Verfahren" gerügt und geltend gemacht, das exorbitant hohe Prozessrisiko vereitele ihr Verbandsbeschwerderecht. In dieser Situation wäre es für die Beschwerdeführer möglich und zumutbar gewesen, einen Betrag zu nennen, ab welchem die Gebühr ihres Erachtens Verfassungsrecht verletzt bzw. die Ausübung des Verbandsbeschwerderechts übermässig erschwert.
Unter diesen Umständen war das Beharren auf einem bezifferten Rechtsbegehren nicht überspitzt formalistisch.
4.3 Zu prüfen ist noch, ob die vom Verwaltungsgericht gewählte Auslegung des Rechtsbegehrens verfassungsrechtlich haltbar ist.
4.3.1 Zwar widersprach die vom Verwaltungsgericht gewählte Auslegung dem Wortlaut des Antrags: Wer eine Herabsetzung "deutlich unter Fr. 10'000.--" verlangt, ist mit einer Herabsetzung "auf Fr. 10'000.--" gerade nicht einverstanden. Für eine andere zahlenmässige Festlegung fehlten jedoch genügende Anhaltspunkte in der Beschwerdeschrift bzw. im angefochtenen Rekursentscheid (vgl. das ähnliche Vorgehen im Urteil 4A_43/2008 vom 4. März 2008 E. 2.2, publ. in: Praxis 97/2008 Nr. 121 S. 756).
4.3.2 Die Beschwerdeführer sind der Auffassung, in dieser Situation wäre das Verwaltungsgericht verpflichtet gewesen, ihnen eine kurze Nachfrist zur Verbesserung des Antrags gemäss § 56 Abs. 1 VRG zu setzen.
Nach dieser Bestimmung prüft der Vorsitzende des Verwaltungsgerichts die eingehenden Beschwerden und ordnet zur Verbesserung allfälliger Mängel das Nötige an. Eine vergleichbare Bestimmung findet sich in § 23 Abs. 2 VRG für das Rekursverfahren.
Nach der Praxis der Zürcher Gerichte muss es sich um formelle Mängel handeln, die nach dem Willen des Gesetzgebers verbesserungsfähig sind. Dies wird v.a. bei Mängeln bejaht, die Gültigkeitsvoraussetzung der Beschwerde bilden, wie z.B. mangelnde Schriftlichkeit, fehlende Unterschrift, fehlende Vollmacht, gänzlich fehlender Antrag oder Begründung, nicht dagegen bei bloss ungenügender Begründung (vgl. KÖLZ/BOSSHART/RÖHL, a.a.O., N. 8 zu § 56 VRG). Rechtskundigen oder rechtskundig vertretenen Beschwerdeführenden wird selbst bei gänzlich fehlendem Antrag und/oder Begründung keine Nachfrist angesetzt, weil es nicht angehe, dass sie sich mittels Verzicht auf Antrag oder Begründung eine Erstreckung der Beschwerdefrist verschafften (KÖLZ/BOSSHART/RÖHL, a.a.O., N. 27 zu § 23 VRG). Diese Praxis wurde vom Bundesgericht mehrfach als verfassungskonform erachtet (vgl. <ref-ruling> E. 3 S. 211 f.; zuletzt bestätigt in Urteil 1C_31/2010 vom 2. Februar 2010 E. 1.4 und 1.5).
Vorliegend waren die Beschwerdeführer vor Verwaltungsgericht anwaltlich vertreten. Sie hatten in der Hauptsache genügend bestimmte Anträge gestellt, weshalb der ungenügend bezifferte Eventualantrag auf Herabsetzung der vorinstanzlichen Gerichtsgebühr keine Gültigkeitsvoraussetzung für die Beschwerde darstellte. Im Übrigen trat das Verwaltungsgericht auch auf diesen Eventualantrag ein, wenn auch mit der Massgabe, dass er auf Fr. 10'000.-- zu beziffern sei. Dieses Vorgehen ist verfassungsrechtlich nicht zu beanstanden.
4.4 Unter diesen Umständen durfte das Verwaltungsgericht ohne Verfassungsverletzung davon ausgehen, dass die Beschwerdeführer eine Herabsetzung der Gebühr auf Fr. 10'000.-- verlangt hatten. Über dieses Rechtsbegehren durften sie gemäss § 63 Abs. 2 VRG nicht hinausgehen. Soweit die Beschwerdeführer dies beanstanden und eine weitergehende Herabsetzung der Gebühr verlangen, ist ihr Begehren unbegründet, soweit darauf überhaupt eingetreten werden kann.
5. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 1'500.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Baukommission Uetikon am See, der Baudirektion, dem Baurekursgericht und dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 28. November 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber