Sachverhalt:
A. Die Beschwerdegegnerin ist seit dem 31. August 2001 im Handelsregister eingetragen, ursprünglich mit der Firma "Z. Q._ AG", seit dem 30. August 2007 mit der (aktuellen) Firma "Z._ AG". Die Beschwerdeführerin 4 beabsichtigt, unter der Firma "Y._ AG" als Bank tätig zu werden. Mit Verfügung vom 8. Dezember 2010 erteilte ihr die FINMA die Bewilligung zur Aufnahme der Geschäftstätigkeit als Bank und Effektenhändlerin unter der genannten Firma. Bereits zuvor, nämlich mit Eingabe vom 25. November 2010, hatte die Beschwerdegegnerin beim Handelsregisteramt des Kantons Zürich Einsprache nach Art. 162 der Handelsregisterverordnung vom 17. Oktober 2007 (HRegV; SR 221.411) gegen die Eintragung einer Aktiengesellschaft mit der Firma "Y._ AG" oder "D. Z._ AG" im Handelsregister erhoben.
B. Am 2. Dezember 2010 ersuchte die Beschwerdegegnerin den Einzelrichter am Handelsgericht des Kantons Zürich um Erlass (vorprozessualer) vorsorglicher Massnahmen. Zur Hauptsache verlangte sie, den Beschwerdeführern sei unter Androhung der Bestrafung gemäss <ref-law> im Falle der Zuwiderhandlung zu verbieten, eine Gesellschaft mit der Firma "Y._ AG" oder "D. Z._ AG" zu gründen und im Handelsregister eintragen zu lassen; zudem sei das Handelsregisteramt des Kantons Zürich anzuweisen, eine von den Beschwerdeführern gegründete Gesellschaft mit der Firma "Y._ AG" oder "D. Z._ AG" bis zum Abschluss des ordentlichen Verfahrens nicht im Handelsregister einzutragen. Mit Verfügung vom 17. Dezember 2010 wies der Einzelrichter das Gesuch ab und wies das Handelsregisteramt des Kantons Zürich an, die Registersperre im Sinne von <ref-law> nach Eintritt der Rechtskraft seines Entscheids aufzuheben.
Dagegen erhob die Beschwerdegegnerin Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich, mit der sie die Aufhebung der angefochtenen Verfügung und die Rückweisung zur Neubeurteilung verlangte. Das Kassationsgericht gelangte in seinem Zirkulationsbeschluss vom 27. Januar 2011 zum Ergebnis, dass der Einzelrichter das rechtliche Gehör der Beschwerdegegnerin verletzt hatte, weil er das Gesuch abgewiesen hatte, ohne der Beschwerdegegnerin zuvor Gelegenheit zu lassen, sich zur beklagtischen Stellungnahme vom 14. Dezember 2010 zu äussern. Die beklagtische Stellungnahme vom 14. Dezember 2010 war der Beschwerdegegnerin am 15. Dezember 2010 zugestellt worden. Bereits am 17. Dezember 2010 fällte der Einzelrichter seine Erledigungsverfügung, so dass die Beschwerdegegnerin aus zeitlichen Gründen nicht hatte replizieren können. Mit Blick auf die Verletzung des rechtlichen Gehörs hiess das Kassationsgericht die Nichtigkeitsbeschwerde gut, hob die angefochtene Verfügung auf und wies die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurück (Dispositiv-Ziffer 1). Die Gerichtsgebühr setzte es auf Fr. 10'000.-- fest (Dispositiv-Ziffer 2) und auferlegte diese je zu einem Viertel und unter solidarischer Haftung den Beschwerdeführern, da sie mit ihrem Rechtsmittelantrag auf Abweisung der Nichtigkeitsbeschwerde unterlegen waren (Dispositiv-Ziffer 3). Ferner verpflichtete es die Beschwerdeführer, der Beschwerdegegnerin für das Kassationsverfahren eine Prozessentschädigung von insgesamt Fr. 5'000.-- zu bezahlen, anteilsmässig zu je einem Viertel und unter solidarischer Haftung (Dispositiv-Ziffer 4).
Am 2. Februar 2011 ersuchten die Beschwerdeführer das Kassationsgericht um Wiedererwägung der Dispositiv-Ziffern 3 und 4 seines Zirkulationsbeschlusses betreffend Auferlegung der Gerichtsgebühr und der Prozessentschädigung. Mit Schreiben vom 3. Februar 2011 teilte das Kassationsgericht den Beschwerdeführern mit, dass kassationsgerichtliche Erledigungsbeschlüsse nicht in Wiedererwägung gezogen werden könnten.
C. Die Beschwerdeführer beantragen dem Bundesgericht mit Beschwerde in Zivilsachen und subsidiärer Verfassungsbeschwerde, die Ziffern 3 und 4 des Dispositivs des Zirkulationsbeschlusses des Kassationsgerichts vom 27. Januar 2011 aufzuheben und die Gerichtsgebühr sowie die Parteientschädigung auf die Staatskasse zu nehmen.
Die Beschwerdegegnerin verzichtete auf eine Vernehmlassung. Das Kassationsgericht liess sich vernehmen, wobei es die Beschwerde als unbegründet erachtete.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1 S. 103, 470 E. 1 S. 472; <ref-ruling> E. 1).
1.1 Der angefochtene Zirkulationsbeschluss des Kassationsgerichts weist die Sache zur Neubeurteilung im Sinne der Erwägungen an die erste Instanz zurück. Ein Rückweisungsentscheid schliesst das Verfahren nicht ab; es handelt sich dabei um einen Zwischenentscheid im Sinne von <ref-law> (BGE <ref-ruling> E. 1.2, 329 E. 1.2; <ref-ruling> E. 1.1 mit Hinweis). Nach der Praxis des Bundesgerichts gilt auch die Regelung der Kosten- und Entschädigungsfolgen in einem Rückweisungsentscheid als Zwischenentscheid (<ref-ruling> E. 1.2 mit Hinweisen). Daran ändert nichts, dass für das Beschwerdeverfahren vor dem Kassationsgericht endgültig über die Kosten entschieden wurde. Die Regelung der Kosten- und Entschädigungsfolgen ist immer ein Nebenpunkt zur Hauptsache (vgl. <ref-law>). Aus diesem Grund bildet die Kosten- und Entschädigungsregelung in einem Rückweisungsentscheid ebenfalls nur einen Zwischenentscheid (<ref-ruling> E. 1.2 S. 331; <ref-ruling> E. 2.1 S. 647).
1.2 Gegen selbständig eröffnete Zwischenentscheide, die weder die Zuständigkeit noch den Ausstand betreffen, ist die Beschwerde nur zulässig, wenn sie einen nicht wieder gutzumachenden Nachteil bewirken können (<ref-law>) oder wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (<ref-law>).
Die Voraussetzung nach <ref-law> ist vorliegend offensichtlich nicht gegeben und wird in der Beschwerde auch nicht geltend gemacht. Die Beschwerdeführer berufen sich auf einen nicht wieder gutzumachenden Nachteil. Ohne Erfolg: Das Bundesgericht hat entschieden, dass der in einem Zwischenentscheid enthaltene Entscheid über die Kosten- und Entschädigungsfolgen nicht geeignet ist, einen nicht wieder gutzumachenden Nachteil zu bewirken. Ein unmittelbarer Weiterzug desselben an das Bundesgericht ist demnach nur im Rahmen einer Beschwerde gegen den Zwischenentscheid im Hauptpunkt zulässig, vorausgesetzt diese steht nach <ref-law> offen. Ansonsten können Kosten- und Entschädigungsfolgen nur gemäss <ref-law> mit Beschwerde gegen den Endentscheid angefochten werden (<ref-ruling> E. 1.2.2; <ref-ruling> E. 2.1).
Die Beschwerdeführer fechten den Kosten- und Entschädigungsentscheid nicht im Rahmen einer Beschwerde gegen den Zwischenentscheid im Hauptpunkt (Rückweisungsentscheid) an, und zwar zu Recht, da der Rückweisungsentscheid nicht selbständig anfechtbar wäre. Diese Konstellation einer möglichen Anfechtung liegt somit nicht vor.
Jedoch ist zwischenzeitlich der Endentscheid in der Hauptsache ergangen. Die Beschwerdeführer legen die Verfügung des Einzelrichters am Handelsgericht des Kantons Zürich vom 17. Februar 2011 ins Recht, wonach dieser das Verfahren unter Kosten- und Entschädigungsfolgen zulasten der Beschwerdegegnerin abgeschrieben hat, nachdem diese ihr Gesuch um Erlass vorsorglicher Massnahmen mit Eingabe vom 15. Februar 2011 zurückgezogen hatte. Zur Anfechtung dieser sie nicht belastenden Endverfügung haben die Beschwerdeführer keinen Anlass. Ihre Beschwerde vom 28. Februar 2011 gegen den im Zwischenentscheid des Kassationsgerichts enthaltenen Kosten- und Entschädigungsentscheid kann unter diesen Umständen als Beschwerde gemäss <ref-law> im Anschluss an den Endentscheid vom 17. Februar 2011 betrachtet werden (vgl. dazu das Urteil 2C_759/2008 vom 6. März 2009 E. 2.6/2.7, in: ASA 79/2010 S. 595 ff.), auch wenn sie nicht ausdrücklich als solche bezeichnet wurde. Denn sonst wäre eine Anfechtung dieses Kosten- und Entschädigungsspruchs nicht möglich.
1.3 Nach dem Grundsatz der Einheit des Prozesses ist der Zwischenentscheid nur mit Beschwerde anfechtbar, wenn es auch der Endentscheid ist (<ref-ruling> E. 3 S. 144; <ref-ruling> E. 2.2). Der Streitwert in der Hauptsache, der auch bei ausschliesslicher Anfechtung des Kosten- und Entschädigungspunktes eines Entscheids massgebend ist (<ref-ruling>), übersteigt nach den Angaben der Vorinstanz die Grenze von Fr. 30'000.-- (<ref-law>). Demnach ist die Beschwerde in Zivilsachen zulässig, so dass die ebenfalls erhobene subsidiäre Verfassungsbeschwerde ausscheidet und nicht darauf einzutreten ist (<ref-law>).
1.4 Auch die Beschwerdegründe können im Beschwerdeverfahren gegen Zwischenentscheide nicht weiter gehen als im Hauptverfahren. Sind die Beschwerdegründe im Hauptverfahren beschränkt (<ref-law>), sind sie es daher auch im Verfahren betreffend Anfechtung eines Zwischenentscheids (Urteil 5A_108/2007 vom 11. Mai 2007 E. 1.2). In der Hauptsache ging es um den Erlass vorsorglicher Massnahmen. Nach <ref-law> kann mit der Beschwerde gegen Entscheide über vorsorgliche Massnahmen nur die Verletzung verfassungsmässiger Rechte gerügt werden. Diese Beschränkung gilt auch für die Anfechtung von Zwischenentscheiden im Rahmen von Verfahren über vorsorgliche Massnahmen. Die Beschwerdeführer rügen eine Verletzung des rechtlichen Gehörs, des Verbots des überspitzten Formalismus und des Grundsatzes der Waffengleichheit (<ref-law>, Art. 6 Ziff. 1 EMRK) sowie des Willkürverbots (<ref-law>). Sie erheben damit zulässige Beschwerdegründe.
1.5 Nach <ref-law> prüft das Bundesgericht die Verletzung von Grundrechten nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist. Der Beschwerdeführer muss klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darlegen, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 1.3.1; <ref-ruling> E. 3.2; <ref-ruling> E. 2.1; <ref-ruling> E. 3.1 S. 399; <ref-ruling> E. 2 S. 591 f., je mit Hinweisen). Macht der Beschwerdeführer beispielsweise eine Verletzung von <ref-law> geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich. Er hat vielmehr im Einzelnen aufzuzeigen, inwiefern der angefochtene Entscheid offensichtlich unhaltbar ist (<ref-ruling> E. 3 S. 352; <ref-ruling> E. 5.5 S. 5; <ref-ruling> E. 1.3 S. 262). Auf Rügen, die diese Begründungsanforderungen nicht erfüllen, ist nicht einzutreten.
1.6 Zusammenfassend folgt, dass auf die Beschwerde in Zivilsachen - unter Vorbehalt einer rechtsgenüglichen Begründung (<ref-law>) - einzutreten ist.
2. Die Vorinstanz auferlegte den Beschwerdeführern die Gerichtsgebühr für das Kassationsverfahren mit der Begründung, entsprechend der auch im Rechtsmittelverfahren geltenden allgemeinen Regel von § 64 Abs. 2 der (auf den 1. Januar 2011 aufgehobenen) Zivilprozessordnung des Kantons Zürich (aZPO/ZH) seien die Gerichtskosten den mit ihrem Rechtsmittelantrag (auf Abweisung der Beschwerde) unterliegenden Beschwerdeführern (im vorinstanzlichen Verfahren: Beschwerdegegner) aufzuerlegen. Zudem hätten sie (als kostenpflichtige Partei) der Beschwerdegegnerin (im vorinstanzlichen Verfahren: Beschwerdeführerin) eine Prozessentschädigung zu bezahlen (§ 68 Abs. 1 aZPO/ ZH). Die Vorinstanz verteilte die Kosten und Entschädigung demnach gemäss dem Erfolgsprinzip. Eine solche Kostenverteilung ist verfassungsrechtlich nicht zu beanstanden, wie das Bundesgericht bereits Gelegenheit hatte festzuhalten (<ref-ruling>). Was die Beschwerdeführer dagegen vorbringen, verfängt nicht:
3. 3.1 Sie rügen eine Verletzung ihres Gehörsanspruchs (<ref-law>, Art. 6 Ziff. 1 EMRK). Die Vorinstanz habe in der Antwort auf ihr Wiedererwägungsgesuch argumentiert, massgeblicher Auslöser der Kostenauflage und der damit einhergehenden Entschädigungspflicht sei nicht der Fehler der Erstinstanz gewesen, sondern der Umstand, dass die Beschwerdeführer (sogar noch vor einer diesbezüglichen gerichtlichen Fristansetzung) von ihrem Recht auf freigestellte Beantwortung der Beschwerde Gebrauch gemacht und in ihrer Antwort den Antrag auf Abweisung der Beschwerde gestellt hätten. Die Beschwerdeführer argumentieren, es stelle eine Verletzung der grundrechtlich geschützten Verfahrensgarantien dar, wenn ihnen einzig deshalb die Kosten auferlegt würden, weil sie ihr rechtliches Gehör wahrgenommen hätten. Eine solche Kostenregelung, die eine Partei praktisch dazu zwinge, auf eine Antwort zu verzichten, wolle sie nicht entschädigungspflichtig werden, komme einer Bestrafung für die Ausübung eines verfassungsmässig garantierten Rechts gleich. Nehme sie im Rahmen ihres Gehörsanspruchs Stellung, riskiere sie, für einen von ihr nicht verursachten Fehler der Vorinstanz kosten- und entschädigungspflichtig zu werden, obschon sie in der Sache an sich obsiege.
3.2 Der Anspruch auf rechtliches Gehör nach <ref-law> verleiht dem Einzelnen insbesondere das Recht, sich vor der zuständigen Behörde in ausreichender Weise äussern und seinen Standpunkt wirksam ins Verfahren einbringen zu können (<ref-ruling> E. 2.2.1 S. 188; <ref-ruling> E. 5.1; <ref-ruling> E. 2b, je mit Hinweisen). Hingegen folgt aus <ref-law> grundsätzlich kein Anspruch darauf, sich ohne Kostenrisiko äussern zu können und nicht mit Kosten belastet zu werden, wenn der gestellte Antrag nicht obsiegt.
3.3 Die Beschwerdeführer wurden nicht deshalb mit Kosten- und Entschädigungsfolgen belastet, weil sie von ihrem Äusserungsrecht Gebrauch gemacht haben, sondern weil sie mit ihrem Rechtsmittelantrag auf Abweisung der Beschwerde unterlegen sind. Dabei ist es durchaus üblich und kommt auch im bundesgerichtlichen Beschwerdeverfahren vor (vgl. z.B. Urteil 4A_479/2010 vom 17. Februar 2011 E. 5), dass die Frage des Obsiegens und Unterliegens für das Rechtsmittelverfahren gesondert betrachtet wird. Es ist insofern ohne Belang, dass die Beschwerdeführer möglicherweise im späteren wieder aufgenommenen Verfahren vor der ersten Instanz, an welche die Sache zur Neubeurteilung zurückgewiesen wurde, obsiegten.
Ebenso wenig verbietet sich eine Kostenauflage deshalb, weil das Kassationsgericht die Beschwerde wegen eines Verfahrensfehlers des Vorderrichters (Verletzung des Gehörsanspruchs der Beschwerdegegnerin) gutgeheissen hat. Die Beschwerdeführer wurden nicht wegen des Verfahrensfehlers des Richters mit Kosten belastet, sondern weil sie die Abweisung der Beschwerde beantragten und sich damit mit dem angefochtenen (fehlerhaften) Entscheid identifizierten, mit welchem Rechtsmittelantrag sie unterlagen. Im Zivilprozess bildet das Erfolgsprinzip den Hauptgrundsatz für die Kostenverteilung. Es beruht auf der Vermutung, dass die unterliegende Partei die Kosten verursacht hat. Die Kostenverursachung ist dabei nicht in einem engen Sinn zu verstehen, wonach eine Partei nur solche Kosten zu tragen hat, die durch ihr Verhalten unmittelbar entstanden sind (<ref-ruling> E. 6b S. 2 f.). Die Aufhebung eines Entscheids in einem Kassationsverfahren - wie in jedem Rechtsmittelverfahren überhaupt - beruht regelmässig auf einem Fehler des Vorderrichters (Setzung eines Nichtigkeitsgrundes oder unrichtige Rechtsanwendung) und nicht auf einem solchen der Parteien. Wer aber ein Rechtsmittel ergreift oder sich auf ein Rechtsmittelverfahren einlässt und entsprechende Rechtsmittelanträge stellt, trägt das damit verbundene allgemeine Prozessrisiko. Er hat mit seinem Unterliegen zu rechnen und die damit verbundenen Kostenfolgen zu tragen (in diesem Sinne <ref-ruling> E. 6b S. 3). Es kann daher nicht gesagt werden, die Belastung der mit ihrem Rechtsmittelantrag auf Abweisung der Beschwerde unterlegenen Beschwerdeführer mit den Kosten- und Entschädigungsfolgen "bestrafe" sie für die Wahrnehmung ihres Äusserungsrechts. Vielmehr liegt darin eine folgerichtige Anwendung des Erfolgsprinzips.
Die Rüge einer Verletzung des rechtlichen Gehörs der Beschwerdeführer geht daher fehl.
4. 4.1 Weiter werfen die Beschwerdeführer der Vorinstanz eine Verletzung der Begründungspflicht vor, weil sie in ihrer Antwort vom 3. Februar 2011 auf das Wiedererwägungsgesuch entgegnet habe, die getroffene Kosten- und Entschädigungsregelung entspreche der ständigen Praxis der Vorinstanz. Weder im angefochtenen Beschluss noch im Schreiben vom 3. Februar 2011 mache die Vorinstanz einschlägige Verweise auf ihre angebliche ständige Praxis. Sie verletze daher auch in dieser Hinsicht das rechtliche Gehör der Beschwerdeführer.
4.2 Die im Gehörsanspruch enthaltene Begründungspflicht verlangt von der Behörde, ihren Entscheid so zu begründen, dass der Betroffene den Entscheid gegebenenfalls sachgerecht anfechten kann. Die Begründung muss kurz die wesentlichen Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die es seinen Entscheid stützt. Nicht erforderlich ist, dass sich die Begründung mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt (<ref-ruling> E. 2.2.1 S. 188 mit Hinweisen). Der Entscheid über die Höhe der Parteientschädigung muss in der Regel nicht begründet werden (<ref-ruling>).
4.3 Die Vorinstanz hat die getroffene Kosten- und Entschädigungsverteilung im angefochtenen Zirkulationsbeschluss begründet, indem sie auf die anwendbaren Normen der aZPO/ZH hinwies und ausführte, dass die Beschwerdeführer als unterliegende Parteien zu betrachten seien, da sie mit ihrem Antrag auf Abweisung der Beschwerde nicht durchgedrungen seien. Damit hat sie die getroffene Kosten- und Entschädigungsregelung hinlänglich begründet. Ob die Ausführungen der Vorinstanz in ihrem Antwortschreiben vom 3. Februar 2011 auf das Wiedererwägungsgesuch der Begründungspflicht nach <ref-law> genügen, ist vom Bundesgericht nicht zu prüfen, da Anfechtungsobjekt einzig der Zirkulationsbeschluss vom 27. Januar 2011 bildet (bzw. Teile davon) und nicht das Antwortschreiben vom 3. Februar 2011. Im Zirkulationsbeschluss vom 27. Januar 2011 konnte und musste die Vorinstanz auch nicht Stellung beziehen zu den von den Beschwerdeführern in ihrem später verfassten Wiedererwägungsgesuch vom 2. Februar 2011 angerufenen Entscheiden des Kassationsgerichts Nr. AA090086 und Nr. AA050183. Eine Verletzung der Begründungspflicht lässt sich von vornherein nicht damit begründen, dass die Vorinstanz sich nicht mit einem erst nach Erlass des angefochtenen Entscheids vorgebrachten Argument auseinandergesetzt hat.
Die Begründung des Kostenentscheids des angefochtenen Zirkulationsbeschlusses entspricht den verfassungsrechtlichen Anforderungen, weshalb auch insofern keine Verletzung des Gehörsanspruchs gegeben ist.
5. 5.1 Die Beschwerdeführer erblicken in der gerügten Kosten- und Entschädigungsregelung auch einen Verstoss gegen das Verbot des überspitzten Formalismus. Die "sture" Anwendung des allgemeinen Grundsatzes der Kostenverteilung (§ 64 Abs. 2 Satz 1 aZPO/ZH) sei nicht durch schutzwürdige Interessen gedeckt, stelle reinen Selbstzweck dar und erschwere in unhaltbarer Weise die Verwirklichung des materiellen Rechts. Die Beschwerdeführer seien unfreiwillig in den Prozess gezogen worden, trügen absolut kein Verschulden am Behördenfehler und hätten in der Hauptsache obsiegt. Trotzdem würden sie kosten- und entschädigungspflichtig. Damit werde die Durchsetzung des materiellen Rechts, nämlich dass derjenige, der ungerechtfertigt in einen Prozess verwickelt werde, keinen Schaden erleide, verletzt (recte wohl: vereitelt). Sodann sei nicht ersichtlich, weshalb die Vorinstanz die allgemeine Verteilungsregel nach § 64 Abs. 2 aZPO/ZH angewendet habe, anstatt "einschlägigere" Bestimmungen zur Verteilung der Kosten anzuwenden, wie § 64 Abs. 3 aZPO/ZH, wonach vom allgemeinen Grundsatz abgewichen werden könne, wenn die unterliegende Partei sich in guten Treuen zur Prozessführung veranlasst gesehen habe, oder § 66 Abs. 2 aZPO/ZH, wonach Kosten, die von keiner Partei veranlasst worden seien, in der Regel auf die Gerichtskasse genommen würden.
5.2 Überspitzter Formalismus als besondere Form der Rechtsverweigerung 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).
5.3 Die Berufung auf das Verbot des überspitzten Formalismus geht hier an der Sache vorbei. Die Vorschriften über die Gerichtskosten und Prozessentschädigungen nach § 64 ff. aZPO/ZH, auf die sich der angefochtene Kostenentscheid stützt, stellen keine Formvorschriften dar, gegen deren zu rigorose Anwendung sich das genannte Verbot richtet. Die Beschwerdeführer müssten eine willkürliche Anwendung der herangezogenen Vorschriften aufzeigen oder dartun können, weshalb die Nichtanwendung der von ihnen angerufenen Ausnahmebestimmungen gegen das Willkürverbot verstösst (dazu Erwägung 7). Eine übertriebene Formstrenge ist im vorliegenden Zusammenhang dagegen nicht ersichtlich.
6. 6.1 Die Beschwerdeführer halten die gerügte Kostenverteilung ferner mit dem Grundsatz der Waffengleichheit für unvereinbar. Sie hätten aufgrund der nicht zu erwartenden Gehörsverletzung des Einzelrichters und der Praxis der Kostenverteilung der Vorinstanz von Anfang an nie die Möglichkeit gehabt, eine Stellungnahme zur Nichtigkeitsbeschwerde der Beschwerdegegnerin abzugeben, ohne kostenpflichtig zu werden. Damit sei ihr Anspruch auf prozessuale Chancengleichheit im Sinne des Grundsatzes der Waffengleichheit verletzt worden.
6.2 Der Grundsatz der Waffengleichheit bildet einen Teilgehalt des Rechts auf ein faires Verfahren (<ref-law>, Art. 6 Ziff. 1 EMRK). Er garantiert, dass sich alle Parteien mit "gleich langen Spiessen" am Verfahren beteiligen können, insbesondere mit gleichem Recht auf Aktenzugang und Teilnahme am Beweisverfahren und zwar zu Bedingungen, die keinen wesentlichen Nachteil gegenüber der Gegenpartei darstellen (BGE <ref-ruling> E. 5.3.1; <ref-ruling> E. 2b S. 163). Er soll nicht nur eine formale Gleichheit der prozessualen Rechtspositionen der Parteien gewährleisten sondern weiter gehend auch ihre durch das Gericht zu verwirklichende materielle Gleichwertigkeit im Sinne einer prozessualen Chancengleichheit. Allerdings verpflichtet Art. 6 Ziff. 1 EMRK die Vertragsstaaten nicht, eine vollständige Waffengleichheit zwischen den Parteien herzustellen. Aus der Konvention ergibt sich jedoch ein Anspruch der Partei, nicht in eine prozessuale Lage versetzt zu werden, aus der sie keine vernünftige Chance hat, ihre Sache dem Gericht zu unterbreiten, ohne gegenüber den anderen Verfahrensbeteiligten klar benachteiligt zu sein (<ref-ruling> E. 4.3.1 mit Hinweisen auf die Rechtsprechung des EGMR).
6.3 Eine prozessuale Ungleichbehandlung in diesem Sinne oder eine Benachteiligung der Beschwerdeführer ist nicht auszumachen. Nicht allein die Beschwerdeführer gingen ein Kostenrisiko ein, indem sie zur Nichtigkeitsbeschwerde Stellung nahmen und deren Abweisung beantragten. Auch die Beschwerdegegnerin riskierte gleich wie die Beschwerdeführer, mit den Kosten- und Entschädigungsfolgen belastet zu werden, als sie Nichtigkeitsbeschwerde erhob auf die Gefahr hin, dass das Kassationsgericht das Vorliegen eines Nichtigkeitsgrundes verneinen, und demnach die Beschwerdegegnerin als unterliegende Partei gelten würde. In Bezug auf die Regelung der Kosten- und Entschädigungsfolgen herrschten im vorinstanzlichen Verfahren "gleich lange Spiesse". Beide Parteien trugen gleichermassen ein Kostenrisiko und waren insofern im Verfahren gleichgestellt. Die Rüge einer Verletzung des Grundsatzes der Waffengleichheit ist unbegründet.
7. 7.1 Die Beschwerdeführer machen schliesslich einen Verstoss gegen das Willkürverbot (<ref-law>) geltend. Es widerstrebe in stossender Weise dem Gerechtigkeitsempfinden, dass, obschon der Grund für die Gutheissung der Nichtigkeitsbeschwerde ein klarer Behördenfehler gewesen sei, den Beschwerdeführern die Gerichtskosten sowie die Prozessentschädigung auferlegt worden sei, nur weil sie in guten Treuen Stellung genommen und rasch eine Beschwerdeantwort eingereicht hätten. Es sei offensichtlich unhaltbar, dass eine Partei, die unfreiwillig in ein Verfahren hineingezogen worden sei und zum Schluss "auf der ganzen Linie Recht erhalten" habe, am Ende Prozesskosten zu tragen habe, die sie in keiner Weise verursacht habe. Damit werde auch dem Verursacherprinzip widersprochen. Es sei nicht ersichtlich, weshalb die Kostenverteilung anders gehandhabt werde als etwa in Fällen falscher Rechtsmittelbelehrungen, in denen ebenfalls Behördenfehler ursächlich seien für die Prozesskosten, in welchen Fällen aber die Prozesskosten seit jeher von der Staatskasse getragen würden, wie etwa schon in BGE 76 I 189 f. Dem Gerechtigkeitsempfinden um Einiges mehr entsprechen würde alternativ, wenn über die Regelung der Kosten- und Entschädigungsfolgen des Verfahrens vor der Vorinstanz nicht gesondert entschieden würde, sondern dem neuen Entscheid des Einzelrichters des Handelsgerichts vorbehalten bliebe. So wiesen andere Rechtsmittelinstanzen im Rahmen von Rückweisungsbeschlüssen regelmässig auch die Regelung der Kosten- und Entschädigungsfolgen an die entsprechende Vorinstanz zurück. So gesehen, verstosse der Entscheid der Vorinstanz auch gegen den Gleichbehandlungsgrundsatz nach <ref-law>. Es sei willkürlich und verletze die angerufenen Verfahrensgarantien, wenn die Vorinstanz sich bei der Verteilung der Prozesskosten einzig auf die allgemeine Regel gemäss § 64 Abs. 2 Satz 1 aZPO/ZH stütze, anstatt die um "einiges einschlägigeren" §§ 64 Abs. 3 oder 66 Abs. 2 aZPO/ZH anzuwenden.
7.2 Nach ständiger Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid 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. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 mit Hinweisen).
7.3 Willkür in diesem Sinn wird von den Beschwerdeführern nicht aufgezeigt. Sie wiederholen weitgehend ihre Argumentation, dass sie in guten Treuen von ihrem Äusserungsrecht Gebrauch gemacht hätten, dass nicht sie sondern ein Behördenfehler die Prozesskosten verursacht hätten und dass die Frage des Obsiegens und Unterliegens nicht separat für das Kassationsverfahren sondern zusammen mit der Neubeurteilung der Hauptsache zu beurteilen sei. Wie in Erwägung 3 erläutert, vermögen die Beschwerdeführer damit keine Verletzung des Anspruchs auf rechtliches Gehör zu begründen. Sie zeigen mit ihrer Argumentation aber auch keine willkürliche Rechtsanwendung auf. Das Bundesgericht hat sich in <ref-ruling> in einer analogen Konstellation mit dieser Argumentation auseinandergesetzt und dazu was folgt erwogen (E. 6b):
"b) Der Beschwerdeführer hat im Rechtsmittelverfahren die Abweisung der Kostenbeschwerde beantragt. Das Obergericht heisst die Beschwerde jedoch gut und legt die Kosten gemäss der allgemeinen Kostenverteilungsregel von <ref-law> AG dem Beschwerdeführer als unterliegende Partei auf. Diese Kostenauflage widerspricht dem Willkürverbot nicht. Im Zivilprozess gilt als Hauptgrundsatz für die Kostenverteilung das Erfolgsprinzip (GULDENER, Schweizerisches Zivilprozessrecht, 3. Aufl. 1979, S. 406; VOGEL, Grundriss des Zivilprozessrechts, 3. Aufl. 1992, S. 262 N. 24). Dieses beruht auf der Vermutung, dass die unterliegende Partei die Kosten verursacht hat (HUGO CASANOVA, Die Haftung der Parteien für prozessuales Verhalten, Diss. Freiburg 1982, S. 24; GUIDO ENRIQUE FISCHER, Die Kostenverteilung im aargauischen Zivilprozessrecht, Diss. Basel 1984, S. 10). Die Kostenverursachung ist dabei nicht in einem engen Sinn zu verstehen, wonach eine Partei nur solche Kosten zu tragen habe, die durch ihr Verhalten unmittelbar entstanden sind. Darunter fallen vielmehr auch Kosten, die durch Massnahmen des Richters im Interesse oder auf Antrag einer Partei veranlasst worden sind. Wer ein Rechtsmittel ergreift oder sich auf ein Rechtsmittelverfahren einlässt und entsprechende Rechtsbegehren stellt, hat mit seinem Unterliegen zu rechnen und die damit verbundenen finanziellen Folgen zu tragen. Will eine Partei ein solches Prozessrisiko nicht auf sich nehmen, hat sie sich vom Prozess zu distanzieren. Es steht ihr frei, sich am Rechtsmittelverfahren nicht zu beteiligen und auf eine Stellungnahme zu verzichten. Vorliegend hat der Beschwerdeführer am Beschwerdeverfahren teilgenommen, Abweisung der Beschwerde beantragt und dies auch eingehend begründet, obwohl der Ausgang des Rechtsmittelverfahrens für ihn eigentlich nicht von Interesse war. Durch seine Teilnahme am Rechtsmittelverfahren hat er damit auch das Risiko auf sich genommen, im Falle der Gutheissung der Beschwerde mit seinem Antrag zu unterliegen und kostenpflichtig zu werden. Die Frage, welche Partei unterlegen ist und damit die Kosten des Verfahrens zu tragen hat, beurteilt sich dabei nach Massgabe des Rechtsbegehrens. Da der Beschwerdeführer auf Abweisung der Beschwerde geschlossen hat, ist er als unterliegende Partei zu betrachten. Auch wenn die gegenteilige Auffassung des Beschwerdeführers und einer Minderheit des Obergerichts ebenfalls vertretbar erscheint, ist die beanstandete Kostenverlegung nicht schon daher willkürlich. Gleich wie das Obergericht verlegt im übrigen auch das Bundesgericht die Kosten. Es auferlegt diese grundsätzlich der unterliegenden Partei. Namentlich im staatsrechtlichen Beschwerdeverfahren wird bei der Kostenverteilung nur darauf abgestellt, welche Partei mit ihrem Antrag unterlegen ist."
Diese Erwägungen treffen auch auf den vorliegenden Fall zu und es ist daran festzuhalten. Gründe für eine abweichende Beurteilung sind nicht dargetan. Der von den Beschwerdeführern angerufene BGE 76 I 187 ist nicht einschlägig. Dort ging es um ein öffentlich-rechtliches Beschwerdeverfahren vor dem Regierungsrat ohne private Gegenpartei. Das Bundesgericht entschied, dass der Partei, die sich in guten Treuen auf eine falsche Rechtsmittelbelehrung (mit zu langer Fristangabe) verlassen hatte, daraus kein Rechtsnachteil erwachsen dürfe, und die dortige Vorinstanz daher unter Zugrundelegung der unzutreffenden Fristangabe das Eintreten auf die erhobene Beschwerde zu prüfen hatte. Über Kosten- und Entschädigungsfolgen wird im veröffentlichten Urteilstext nichts ausgeführt. Dass im Übrigen in einem Fall unrichtiger Rechtsmittelbelehrung die Kosten eines unzulässigen Rechtsmittelverfahrens regelmässig auf die Staatskasse genommen werden, verlangt nicht, dass auch bei Gutheissung einer Nichtigkeitsbeschwerde, der stets ein Behördenfehler zugrunde liegt (Setzung eines Nichtigkeitsgrundes), die Kosten regelmässig zulasten des Staates gehen, selbst wenn sich eine private Gegenpartei mit einem Antrag auf Abweisung der Nichtigkeitsbeschwerde am Kassationsverfahren beteiligt und den angefochtenen Entscheid verteidigt hat. Eine unrichtige Rechtsmittelbelehrung kann unmittelbar dazu führen, dass ein nicht gegebenes Rechtsmittel ergriffen oder von falschen Rechtsmittelvoraussetzungen ausgegangen wird. In einem solchen Fall kann es angezeigt erscheinen, die durch die unrichtige Rechtsmittelbelehrung verursachten Kosten des unzulässigen Rechtsmittelverfahrens auf die Staatskasse zu nehmen. Demgegenüber streiten sich die Parteien, wenn das Kassationsverfahren zulässigerweise eingeleitet wird, um das Vorliegen eines Nichtigkeitsgrundes. Je nach Ausgang des Verfahrens unterliegt die eine oder die andere Partei mit ihrem Beschwerdeantrag. Die gegensätzliche Interessenlage rechtfertigt es hier, die Kostenverteilung anders als in Fällen unrichtiger Rechtsmittelbelehrung, eben nach Massgabe des Unterliegens, vorzunehmen.
Auch die Berufung auf den Gleichheitsgrundsatz verfängt nicht. Es trifft in der gewählten allgemeinen Formulierung nicht zu, dass "andere Rechtsmittelinstanzen im Rahmen von Rückweisungsbeschlüssen regelmässig auch die Regelung der Kosten- und Entschädigungsfolgen an die entsprechende Vorinstanz zurückweisen". So besteht namentlich im bundesgerichtlichen Beschwerdeverfahren keine Möglichkeit, die Kosten eines Rückweisungsentscheids in dem Sinn zur Hauptsache zu schlagen, dass erst mit dem endgültigen Entscheid in der Sache die Kosten verteilt werden (THOMAS GEISER, in: Basler Kommentar, Bundesgerichtsgesetz, 2008, N. 12 zu <ref-law>).
Schliesslich begründen die Beschwerdeführer ihre Willkürrüge nicht erfolgreich (vgl. Erwägung 1.5), wenn sie bloss behaupten, es sei willkürlich, die allgemeine Regel gemäss § 64 Abs. 2 Satz 1 aZPO/ZH statt die um "einiges einschlägigeren" §§ 64 Abs. 3 oder 66 Abs. 2 aZPO/ZH anzuwenden. Es ist nicht dargetan, dass die Voraussetzungen von § 64 Abs. 3 aZPO/ZH oder § 66 Abs. 2 aZPO/ZH vorlagen und sich deren Anwendung aufdrängte, so dass die statt dessen nach der allgemeinen Regel von § 64 Abs. 2 Satz 1 aZPO/ZH vorgenommene Kostenverteilung geradezu unhaltbar wäre. Namentlich muss entgegen den Beschwerdeführern nicht von einer Prozessführung ihrerseits in guten Treuen im Sinne von § 64 Abs. 3 aZPO/ZH ausgegangen werden, weil sie an einer raschen Streiterledigung und Beseitigung der Registersperre interessiert waren und deshalb möglichst rasch (und unaufgefordert) eine Beschwerdeantwort einreichten. Nach den Ausführungen des Kassationsgerichts in seiner Vernehmlassung waren die Beschwerdeführer nicht gezwungen, sich mit ihrem Antrag auf Beschwerdeabweisung einem Kostenrisiko auszusetzen. Sie hätten auch auf eine Beschwerdeantwort verzichten und das Kassationsgericht um eine rasche Entscheidung bitten können, wenn sie - wie sie geltend machen - auf eine möglichst baldige Klärung angewiesen waren (vgl. demgegenüber <ref-ruling>, wonach im bundesgerichtlichen Verfahren die Gegenpartei auch bei Verzicht auf Antragstellung dem Kostenrisiko nicht entgeht). Sodann wurde bereits ausgeführt, dass das Erfolgsprinzip die Kostenverursachung nicht in einem engen Sinn versteht. Der Umstand, dass die Beschwerdeführer die Prozesskosten nicht unmittelbar durch ihr Verhalten verursacht haben, ist daher nicht ausschlaggebend und musste auch nicht zwingend zur Anwendung von § 66 Abs. 2 aZPO/ZH führen, wonach Kosten, die keine Partei veranlasst hat, in der Regel auf die Gerichtskasse genommen werden. Schliesslich ist festzuhalten, dass die beanstandete Kostenverteilung nicht schon dann willkürlich ist, wenn die Vorschriften der aZPO/ZH auch eine andere Kostenregelung zugelassen hätten.
Damit geht auch der Willkürvorwurf fehl.
8. Die Beschwerde in Zivilsachen erweist sich als unbegründet und ist abzuweisen. Bei diesem Verfahrensausgang werden die Beschwerdeführer in solidarischer Haftbarkeit kostenpflichtig (Art. 66 Abs. 1 und 5 BGG). Eine Parteientschädigung ist nicht zu sprechen, da sich die Beschwerdegegnerin nicht vernehmen liess.

Demnach erkennt das Bundesgericht:
1. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Die Beschwerde in Zivilsachen wird abgewiesen.
3. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt, in solidarischer Haftbarkeit.
4. Dieses Urteil wird den Parteien und dem Kassationsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 12. Mai 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Widmer