Sachverhalt:
A. Am 11. Oktober 2010 erliess das Steueramt der Gemeinde A._ gegen X._ und Y._ eine Sicherstellungsverfügung über Fr. 5'160'000.-- zur Deckung der Staats- und Gemeindesteuern 2004 bis 2009. Gegen diese Verfügung führten X._ und Y._ Rekurs beim Verwaltungsgericht des Kantons Zürich. Dieses wies mit Urteil vom 25. Mai 2011 das Rechtsmittel ab, soweit darauf einzutreten war, setzte die Gerichtsgebühr auf Fr. 50'000.-- fest und auferlegte die Kosten (einschliesslich Zustellkosten von Fr. 120.--) den Rekurrenten je zur Hälfte unter solidarischer Haftung für den ganzen Betrag.
Eine Beschwerde in öffentlich-rechtlichen Angelegenheiten hiess das Bundesgericht mit Urteil vom 16. Januar 2012 teilweise gut, hob den Entscheid in Dispositiv-Ziffer 2 (Gerichtskosten) auf und wies die Sache zur Neuregelung der Gerichtsgebühr und der übrigen Kosten (Portopauschalen) an das Verwaltungsgericht zurück. Im Übrigen wurde die Beschwerde abgewiesen.
B. Mit Beschluss vom 11. April 2012 setzte das Verwaltungsgericht des Kantons Zürich die Gerichtsgebühr für das Rekursverfahren neu auf Fr. 25'000.-- und die Zustellkosten auf Fr. 80.-- fest. Eine Parteientschädigung wurde nicht zugesprochen.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen X._ und Y._ dem Bundesgericht, Ziffer 1 des Beschlusses des Verwaltungsgerichts des Kantons Zürich vom 11. April 2012 sei aufzuheben und die Gerichtsgebühr sei auf das zulässige Masse zu reduzieren. Eventualiter sei die Angelegenheit zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen. Gerügt wird eine Verletzung des Anspruchs auf rechtliches Gehör, des Äquivalenzprinzips, der Rechtsweggarantie, des Anspruchs auf ein rasches und wohlfeiles Verfahren (Art. 18 Abs. 1 KV/ZH) sowie des Willkürverbots.
Das Verwaltungsgericht des Kantons Zürich beantragt die Beschwerde abzuweisen, soweit darauf einzutreten sei.

Erwägungen:
1. Beim angefochtenen Urteil handelt es sich um einen Entscheid in Angelegenheiten des öffentlichen Rechts im Sinne von <ref-law>, der nicht unter den Ausnahmekatalog von <ref-law> fällt. Das Verwaltungsgericht des Kantons Zürich ist eine letzte kantonale Instanz im Sinne von <ref-law>, deren Entscheide mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht angefochten werden können. Die Beschwerdeführer sind durch das angefochtene Urteil offensichtlich besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>). Auf die im übrigen form- und fristgerecht eingereichte Beschwerde ist einzutreten.
Vorliegend sind einzig die Gerichtskosten angefochten. Deren Festsetzung richtet sich nach kantonalem Recht. Es kann daher nur geltend gemacht werden, die Kosten- und Entschädigungsregelung gemäss dem angefochtenen Entscheid verstosse gegen verfassungsmässige Rechte und Grundsätze der Bundes- oder Kantonsverfassung (Art. 95 lit. a und c BGG; <ref-ruling> E. 1.2 S. 145; <ref-ruling> E. 4.2.2 S. 158). Hierfür gilt eine gegenüber der allgemeinen Begründungspflicht (<ref-law>) qualifizierte Rügepflicht (<ref-law>).
2. Die Beschwerdeführer rügen eine Verletzung ihres Anspruchs auf rechtliches Gehör (<ref-law>). Sie führen aus, im Anschluss an das Urteil des Bundesgerichts hätten sie beim Verwaltungsgericht am 31. Januar 2012 eine (unverlangte) Stellungnahme eingereicht. Darin hätten sie sich zur Höhe der neu festzusetzenden Gebühr geäussert und geltend gemacht, für die Bestimmung der Gerichtsgebühr könnten "hilfsweise die Bestimmungen für Gerichtsgebühren eines summarischen Verfahrens im Zivilprozessrecht" (§ 8 und 5 der Gebührenverordnung des Obergerichts vom 8. September 2010) herangezogen werden. Auf diese Stellungnahme und deren Argumente sei das Verwaltungsgericht nicht eingegangen.
Das rechtliche Gehör nach <ref-law> verlangt, dass die Behörde die Vorbringen der vom Entscheid in ihrer Rechtslage betroffenen Person auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt. Daraus folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen. Es ist dabei nicht erforderlich, dass sie sich mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Die Begründung muss so abgefasst sein, dass sich die betroffene Person über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann (<ref-ruling> E. 2.2.1, 229 E. 5.2; <ref-ruling> E. 4.2; je mit Hinweisen).
Diesen Anforderungen genügt der angefochtene Beschluss: Die Vorinstanz hat die Stellungnahme der Beschwerdeführer vom 31. Januar 2012 behandelt. Sie hat die darin geäusserte Ansicht der Beschwerdeführer, wonach sich die Gerichtsgebühr höchstens im Rahmen des Kostenvorschusses (Fr. 10'000.--) bewegen dürfe, mit Hinweis auf das Urteil des Bundesgerichts abgelehnt (angefochtener Beschluss E. 2.2 in fine). Die Vorinstanz hat im Übrigen dargelegt, welche Vorschriften sie für die Festsetzung der Kosten des Rekurses im Sicherstellungsverfahren als massgebend erachtet, nämlich die einschlägigen Vorschriften des Zürcher Steuergesetzes vom 8. Juni 1997 (§ 151 in Verbindung mit § 181 Abs. 3 StG) und der Gebührenverordnung des Verwaltungsgerichts vom 23. August 2010. Damit hat die Vorinstanz die Begründung der Beschwerdeführer in der Eingabe vom 31. Januar 2012 (wonach hilfsweise die Vorschriften der Gebührenverordnung des Obergerichts für den Zivilprozess herangezogen werden könnten und die im Übrigen nicht weiter substantiiert worden ist) zumindest implizit widerlegt. Der angefochtene Beschluss genügt damit den Erfordernissen, die <ref-law> an die Begründung von Entscheiden stellt. Der Anspruch auf rechtliches Gehör ist nicht verletzt.
3. Zu prüfen bleiben die Rügen, die sich gegen die Bemessung der Gerichtsgebühr richten.
3.1 Gerichtskosten sind Kausalabgaben, weshalb sie dem Kostendeckungs- und Äquivalenzprinzip genügen müssen (<ref-ruling> E. 3.1; <ref-ruling> E. 4.2 S. 121; <ref-ruling> E. 4a S. 244; <ref-ruling> E. 2a S. 174). Das Äquivalenzprinzip konkretisiert das Verhältnismässigkeitsprinzip und das Willkürverbot für den Bereich der Kausalabgaben (Art. 5 Abs. 2 und Art. 8 BV). Es bestimmt, dass eine Gebühr nicht in einem offensichtlichen Missverhältnis zum objektiven Wert der Leistung stehen darf und sich in vernünftigen Grenzen halten muss. Der Wert der Leistung bemisst sich nach dem wirtschaftlichen Nutzen, den sie dem Pflichtigen bringt, oder nach dem Kostenaufwand der konkreten Inanspruchnahme im Verhältnis zum gesamten Aufwand des betreffenden Verwaltungszweigs, wobei schematische, auf Wahrscheinlichkeit und Durchschnittserfahrungen beruhende Massstäbe angelegt werden dürfen. Es ist nicht notwendig, dass die Gebühren in jedem Fall genau dem Verwaltungsaufwand entsprechen; sie sollen indessen nach sachlich vertretbaren Kriterien bemessen sein und nicht Unterscheidungen treffen, für die keine vernünftigen Gründe ersichtlich sind. Bei der Festsetzung von Verwaltungsgebühren darf deshalb innerhalb eines gewissen Rahmens auch der wirtschaftlichen Situation des Pflichtigen und dessen Interesse am abzugeltenden Akt Rechnung getragen werden. Bei Gerichtsgebühren darf namentlich der Streitwert eine massgebende Rolle spielen (<ref-ruling> E. 2.3 S. 228; <ref-ruling> E. 2a). Die Gebühr darf im Übrigen die Inanspruchnahme bestimmter staatlicher Leistungen nicht verunmöglichen oder übermässig erschweren (Rechtsweggarantie, <ref-law>; vgl. BGE <ref-ruling> E. 2a S. 174 mit Hinweis).
Bei der Festsetzung der Gerichtsgebühr steht dem Verwaltungsgericht aber ein grosser Ermessensspielraum zu. Das Bundesgericht greift bei der Auslegung kantonaler Normen nicht bereits dann ein, wenn sich die Gebühr als unangemessen erweist, sondern nur, wenn Ermessensmissbrauch oder Willkür vorliegt (Urteil 4A_680/2011 vom 2. Dezember 2011 E. 2).
3.2 Die Vorinstanz hat begründet, weshalb nach ihrer Ansicht die Gerichtsgebühr von Fr. 25'000.-- angemessen sei. Gemäss den Vorgaben des Bundesgerichts im Rückweisungsentscheid sei zunächst der hohe Streitwert zu berücksichtigen. Der Umstand, dass sich das Verwaltungsgericht bei der Überprüfung der Sicherstellungsverfügung praxisgemäss auf eine Prima-facie-Würdigung der tatsächlichen Verhältnisse beschränke und Glaubhaftmachung genügen lasse, führe zu einer Reduktion. Unter Berücksichtigung des vergleichsweise hohen Arbeitsaufwandes sei die Gebühr neu auf Fr. 25'000.-- festzusetzen.
Die Beschwerdeführer wenden demgegenüber ein, die von der Vorinstanz festgesetzte Gerichtsgebühr von Fr. 25'000.-- stehe in einem offensichtlichen Missverhältnis zum objektiven Wert der bezogenen Leistung. Es treffe nicht zu, dass die Gerichtsgebühr vorab nach dem Streitwert zu bemessen sei. Das Bundesgericht habe nicht festgelegt, dass es sich hier um ein Verfahren mit Streitwert handle. Es gehe vorliegend weder um das Hauptverfahren (Veranlagungsverfahren) noch um das Vorverfahren (zur Feststellung der Steuerhoheit), sondern lediglich um die Steuersicherung. Der vorliegende Fall sei zudem nicht sehr aufwändig oder besonders schwierig gewesen, zumal vorwiegend Textbausteine verwendet worden seien. Das bei der Gebührenerhebung zu beachtende Äquivalenzprinzip und das Willkürverbot seien verletzt. Gebühren dieser Höhe erschwerten zudem den Zugang zum Gericht und die Ausübung des Gehöranspruchs im Sinne von Art. 29a und 29 BV in übermässiger Weise.
3.3 Dass das Verwaltungsgericht die vorliegende Sache nach den massgebenden Bestimmungen der Gebührenverordnung des Verwaltungsgerichts als ein Verfahren mit bestimmbarem Streitwert behandelt und darauf den nach Streitwert abgestuften Gebührentarif von § 3 Abs. 1 GebV zur Anwendung gebracht hat, ist offensichtlich nicht willkürlich. Dass seine Kognition im Verfahren lediglich eine beschränkte war, hat das Verwaltungsgericht zu Recht als Reduktionsgrund bezeichnet. Indem es massgeblich auf den Streitwert abgestellt hat, hat es den wirtschaftlichen Interessen Rechnung getragen. Ob ein "vergleichsweise hoher Arbeitsaufwand" zu bewältigen war, was die Beschwerdeführer bestreiten, kann offenbleiben, zumal nicht gesagt werden kann, dass vorliegend die Gerichtsgebühr in Abhängigkeit vom Streitwert in keinem vernünftigen Verhältnis zum Aufwand des Gerichtes stehe. Die Gerichtsgebühr in bedeutsamen Fällen darf durchaus auch den Ausfall kompensieren, die dem Gericht bei der Behandlung weniger bedeutsamer Fälle entsteht (<ref-ruling> E. 2.3 S. 228 f. mit Hinweisen). Insofern ging die Vorinstanz von haltbaren Annahmen aus und hat sie ihr Ermessen nicht missbraucht. Es kann angesichts der wirtschaftlichen Situation der Beschwerdeführer auch nicht gesagt werden, dass ihnen durch die Höhe der Gerichtsgebühr der Rechtsweg (<ref-law>) verschlossen blieb oder ungebührlich erschwert wurde.
3.4 Zumindest nicht ausdrücklich berücksichtigt hat die Vorinstanz aber den Umstand, dass den Beschwerdeführern erstmals das rechtliche Gehör gewährt worden war, zumal die Sicherstellungsverfügung selbst nicht mit einer Begründung versehen war und das Verwaltungsgericht über die Steuersicherstellung als erste und einzige kantonale Instanz entschieden hat. Unter diesem Gesichtspunkt hätte sich auch eine niedrigere Gerichtsgebühr rechtfertigen lassen.
Willkür liegt allerdings nicht bereits dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst, wenn er offensichtlich unhaltbar ist, zur 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.4; <ref-ruling> E. 2.2.2. S. 318 f.; <ref-ruling> E. 1.3 S. 4 f.). Dabei greift das Bundesgericht in Ermessensentscheide, zu denen Entscheide über die Höhe der Gerichtsgebühr gehören, nur mit grösster Zurückhaltung ein (Urteil 4A_680/2011 vom 2. Dezember 2011 E. 2). Dafür besteht vorliegend noch kein Anlass. Den Aspekt der Gehörsgewährung weniger zu gewichten als den Streitwert ist nicht unhaltbar, und das Bundesgericht hat von der Vorinstanz bloss verlangt, die Gerichtsgebühr "deutlich niedriger festzusetzen", was geschehen ist.
3.5 Die Beschwerdeführer machen ausserdem eine Verletzung von Art. 18 KV/ZH geltend. Nach dieser Bestimmung hat jede Person Anspruch auf rasche und wohlfeile Erledigung des Verfahrens. Der Begriff "wohlfeil" (nach Duden auch "kostengünstig", "erschwinglich") bedeutet, dass Rechtsuchende auch ohne allzu grosses finanzielles Risiko Zugang zu den Gerichten und Verwaltungsinstanzen haben sollen, und zielt damit auf Verfahren mit kleineren Streitwerten. Er schliesst nicht aus, dass der Gesetzgeber Tarife vorsieht, die sich nach dem Streitwert richten (so Giovanni Biaggini, in: Häner/Rüssli/ Schwarzenbach [Hrsg.], Kommentar zur Zürcher Kantonsverfassung, 2007, N. 19 f. zu Art. 18 KV/ZH, mit Hinweis auf die Materialien).
Die von den Beschwerdeführern angesprochenen Aspekte dieser Verfassungsnorm gehen im Übrigen nicht über die prozessualen Garantien hinaus, die sich bereits aus der Bundesverfassung ergeben, namentlich aus der Rechtsweggarantie von <ref-law> sowie aus dem Kostendeckungs- und dem Äquivalenzprinzip. Auch unter diesem Blickwinkel erweist sich die Beschwerde als unbegründet.
4. Die Beschwerde ist nach dem Gesagten abzuweisen. Da die Beschwerdeführer unterliegen, haben sie die Gerichtskosten zu tragen; sie haften für diese solidarisch (Art. 65 und 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, der Gemeinde A._, dem Kantonalen Steueramt Zürich und dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, schriftlich mitgeteilt.
Lausanne, 11. Dezember 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Wyssmann