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.