Sachverhalt:
A. Die LEGO System A/S (Beklagte, Beschwerdeführerin) gehört zur dänischen LEGO-Gruppe, die seit mehreren Jahrzehnten die bekannten LEGO-Klemmbausteine herstellt. Sie hinterlegte verschiedene Formen ihrer Klemmbausteine beim Eidgenössischen Institut für Geistiges Eigentum (IGE) als dreidimensionale Marken für Spielbausteine (Formmarken Nr. 411 469, 433 265, 433 266, 433 267 und 433 268).
Die MEGA Brands Inc., vormals Mega Bloks Inc. bzw. Ritvik Holdings Inc., (Klägerin, Beschwerdegegnerin) gehört zur kanadischen Ritvik-Gruppe und vertreibt weltweit Spielzeuge. Seit den Achtzigerjahren stellt sie auch Klemmbausteine her, die mit den LEGO-Bausteinen kompatibel sind.
B. B.a Am 9. März 2000 stellte die Klägerin beim Handelsgericht des Kantons Zürich das Rechtsbegehren, es seien die von der Beklagten eingetragenen Formmarken Nr. 411 469, 433 265, 433 266, 433 267 und 433 268 nichtig zu erklären. Mit Urteil vom 17. Dezember 2002 hiess das Handelsgericht die Klage gut und erklärte die fünf Streitmarken für nichtig.
Mit Urteil vom 2. Juli 2003 hiess das Bundesgericht die von der Beklagten erhobene Berufung gegen den Entscheid des Handelsgerichts vom 17. Dezember 2002 teilweise gut und wies die Sache zur Prüfung an das Handelsgericht zurück, ob die von der Beklagten beanspruchten Formen technisch notwendig im Sinne von <ref-law> seien und, falls nicht, ob sich die fraglichen, an sich dem Gemeingut zugehörigen Formen im Verkehr als Unterscheidungsmerkmal für die Spielbausteine der Beklagten durchgesetzt haben (<ref-ruling> ff.).
B.b Mit Beschluss vom 27. Januar 2004 setzte das Handelsgericht der Beklagten Frist an, um - neben den 24 bisher aufgezeigten - weitere gleichwertige Alternativformen aufzuzeigen, wobei es in seinen Erwägungen im Einzelnen festlegte, welche Voraussetzungen diese zu erfüllen hätten, damit sie überhaupt als Alternativen zu den eingetragenen Formen in Frage kämen.
Mit Urteil vom 7. Juli 2004 hiess das Bundesgericht ein Erläuterungsgesuch der Beklagten teilweise gut und erläuterte seinen Rückweisungsentscheid vom 2. Juli 2003 in dem Sinne, dass Alternativformen mit den Formen der Beklagten nicht kompatibel bzw. zusammenbaubar sein müssten (Urteil 4C.86/2004). Das Bundesgericht erwog, die Beklagte bringe in ihrem Erläuterungsgesuch zu Recht vor, das Handelsgericht verkenne mit seinem Beweisbeschluss vom 17. Januar 2004 die Tragweite der Rückweisung. Die vom Bundesgericht angeordnete Rückweisung sei allein zur tatsächlichen Feststellung erfolgt, ob die nach dem handelsgerichtlichen Urteil vom 17. Dezember 2002 bestehenden praktikablen Alternativen zu runden, gefüllten Noppen ebenso praktisch, ebenso solide und mit keinen grösseren Herstellungskosten verbunden seien als die umstrittene, als Marke beanspruchte Form der auf dem Quader aufgesetzten Noppen (Urteil 4C.86/2004 vom 7. Juli 2004 E. 2.1.1 mit Verweis auf <ref-ruling> E. 3.2.4 S. 524).
Mit Urteil vom 7. Juli 2004 hiess das Bundesgericht ein Erläuterungsgesuch der Beklagten teilweise gut und erläuterte seinen Rückweisungsentscheid vom 2. Juli 2003 in dem Sinne, dass Alternativformen mit den Formen der Beklagten nicht kompatibel bzw. zusammenbaubar sein müssten (Urteil 4C.86/2004). Das Bundesgericht erwog, die Beklagte bringe in ihrem Erläuterungsgesuch zu Recht vor, das Handelsgericht verkenne mit seinem Beweisbeschluss vom 17. Januar 2004 die Tragweite der Rückweisung. Die vom Bundesgericht angeordnete Rückweisung sei allein zur tatsächlichen Feststellung erfolgt, ob die nach dem handelsgerichtlichen Urteil vom 17. Dezember 2002 bestehenden praktikablen Alternativen zu runden, gefüllten Noppen ebenso praktisch, ebenso solide und mit keinen grösseren Herstellungskosten verbunden seien als die umstrittene, als Marke beanspruchte Form der auf dem Quader aufgesetzten Noppen (Urteil 4C.86/2004 vom 7. Juli 2004 E. 2.1.1 mit Verweis auf <ref-ruling> E. 3.2.4 S. 524).
B.c B.c.a Das Handelsgericht zog seinen Beschluss vom 27. Januar 2004 in der Folge in Wiedererwägung, formulierte ihn hinsichtlich der Frage der Kompatibilität neu und setzte der Beklagten die Frist zur Nennung von Alternativformen und zum Vorschlag eines Gutachters neu an.
Mit Eingabe vom 15. Oktober 2004 bezeichnete die Beklagte 26 weitere Alternativformen, lehnte den von der Klägerin vorgeschlagenen Gutachter, Prof. A._, ab und schlug ihrerseits ein Gutachter-Team bestehend aus Prof. B._ und C._ vor.
B.c.b Mit Beschluss vom 8. Juli 2005 hielt das Handelsgericht fest, die Beklagte habe nun insgesamt 50 Alternativformen aufgezeigt, von denen sie je geltend mache, sie stellten eine ebenso praktische, ebenso solide und nicht mit höheren Herstellungskosten verbundene Ausführung dar wie die Streitmarken. Die Klägerin bestreite dies und liste für jede dieser Alternativen eine Reihe von Nachteilen gegenüber den Streitmarken auf. Die Beweislast liege bei der Beklagten, der Klägerin stehe der Gegenbeweis für die behaupteten Nachteile offen.
Nachdem mit den Parteien davon auszugehen sei, dass die Gültigkeit aller fünf Streitmarken am sogenannten "Grundbaustein" mit 4 x 2 Noppen abgehandelt werden könne, scheine es angezeigt, auch das Beweisverfahren auf diesen Stein bzw. die dazu aufgezeigten Alternativen zu beschränken.
Als Beweismittel hätten sich die Parteien auf ein Gutachten berufen und je auch Gutachtervorschläge unterbreitet, die von der Gegenseite abgelehnt worden seien; diese Ablehnungen erschienen beidseits unbegründet. Entsprechend sei festzustellen, dass die Parteien gegen die vorgeschlagenen Gutachter nichts vorgebracht hätten, was geeignet wäre, deren Bestellung zu verhindern. Damit die vorzunehmende gutachterliche Beurteilung nicht nur aus universitärer Sicht und auch nicht nur aus der Sicht des Praktikers erfolge, erscheine es angezeigt, das Gutachten durch Prof. A._ und C._ gemeinsam erstellen zu lassen; Letzterer lehnte allerdings auf entsprechende Anfrage des Gerichts hin aufgrund anderweitiger zeitlicher Beanspruchung ab.
Mit Verfügung vom 30. August 2005 wurde den Parteien als Praktiker des Gutachter-Teams D._, Werkzeugmacher und Kunststoffingenieur HTL, Inhaber der D._ AG, die sich mit Formenbau und Kunststofftechnik befasst, vorgeschlagen.
Am 9. Februar 2006 erfolgte der Beweisabnahmebeschluss. Während sich die Beweismittel der Klägerin auf das Gutachten beschränkten, wurden bei der Beklagten zusätzlich noch gewisse Urkunden und die Zeugenaussage von E._ (des ehemaligen Entwicklungsleiters der Beklagten) als Beweismittel abgenommen. Sodann wurde mit einlässlicher Begründung D._ als zweiter Gutachter neben Prof. A._ bestellt. Weiter stellte das Handelsgericht den Parteien den Entwurf der Experteninstruktion zur Stellungnahme zu.
Am 24. März bzw. 27. April 2006 erfolgten die Stellungnahmen der Parteien zum Entwurf der Experteninstruktion.
Anlässlich der Beweisverhandlung vom 17. Mai 2006, die auf Antrag der Beklagten vor dem Kollegialgericht durchgeführt wurde, erfolgte vorab die Einvernahme des Zeugen E._ und eine provisorische Stellungnahme der Parteien dazu. Anschliessend erläuterte der Instruktionsrichter den Parteien, wie weit ihre Anträge bezüglich Änderungen der Experteninstruktion berücksichtigt worden seien. Danach erfolgte die Instruktion der Experten Prof. A._ und D._. Den Experten wurden namentlich die Fragen unterbreitet, ob jede der 50 Alternativen ebenso praktisch (Frage 1), ebenso solide (Frage 2) und nicht mit höheren Herstellungskosten verbunden (Frage 3) sei wie die Streitmarken.
Auf Meinungsäusserung der beiden eingesetzten Gutachter hin wurde am 12. März 2007 mit Zustimmung der beiden Parteien C._ als zusätzlicher Experte für die Beurteilung der Herstellungskosten und für die Vornahme der Bauteilabrechnungen der Alternativformen bestellt.
Die Instruktion von C._ erfolgte am 31. Mai 2007, gefolgt von einer Diskussion mit den Parteien und den drei Gutachtern über das einzuschlagende Prüfungsverfahren. Gericht, Gutachter und Parteien einigten sich dabei auf den Versuchsablauf, in dessen Rahmen im Kunststoff Ausbildungs- und Technologie-Zentrum (KATZ), Aarau, alternative Bausteine produziert werden und anschliessend durch die Gutachter geprüft werden sollten.
Am 17. Januar 2008 fand eine weitere Beweisverhandlung statt, an der im Beisein der Parteien und der drei Gutachter die Materiallieferungen protokolliert und die Versuchsumgebung sowie die zu verwendenden Maschinen von den Parteien genehmigt wurden.
In der Folge wurde von den Gutachtern - in Rücksprache mit dem Gericht und unter Mithilfe der Parteien - am 14. Juli 2008 der definitive Vorschlag für den Produktionsablauf am KATZ, mit Start im September 2008, unterbreitet. Das Gericht stellte diesen Vorschlag den Parteien am 17. Juli 2008 zur Stellungnahme zu.
Innert Frist reichten die Parteien mit Eingaben vom 30. Juli 2008 ihre Stellungnahmen ein. Während die Beklagte ihr Einverständnis mit dem Vorschlag der Experten erklärte, brachte die Klägerin eine Reihe von Bemerkungen an. Mit Verfügung vom 11. August 2008 begründete der Instruktionsrichter, weshalb die klägerischen Bemerkungen keine Änderungen des Vorschlags der Gutachter für den Produktionsablauf rechtfertigten.
Am 29./30. April 2009 wurden im Beisein der Parteien Vorversuche durchgeführt und am 25. Mai 2009 die Produktion aufgenommen.
Am 29. Juli 2009 fand im Beisein der Parteien an der ETH die Versuchsaufnahme der sogenannten "Clutch Power"-Messungen statt.
B.c.c Am 26. August 2009 schlugen die Gutachter Praxisversuche für das Erodierverfahren vor, die den Parteien am 28. August 2009 zur Erhebung von Einwendungen zugestellt wurden, worauf die Parteien am 31. August bzw. 2. September 2009 ihre Zustimmung erteilten.
Am 31. Mai 2010 erstatteten die Gutachter Prof. A._, C._ und D._ ihr Gutachten. Mit Verfügung vom 25. Juni wurde das Gutachten den Parteien zugestellt und ihnen Frist angesetzt, zum Beweisergebnis und insbesondere zum Gutachten Stellung zu nehmen und dessen Erläuterung oder Ergänzung oder die Bestellung anderer Sachverständiger zu beantragen.
Mit Eingabe vom 15. September 2010 reichte die Klägerin ihre Stellungnahme mit Ergänzungsfragen zum Gutachten ein. Am 22. Oktober 2010 nahm die Beklagte zum Beweisergebnis und zum Gutachten Stellung und stellte einige Zusatzfragen. Mit Eingabe vom 21. November 2011 nahm die Beklagte Stellung zur Eingabe der Klägerin vom 15. September 2010.
B.c.d Mit Urteil vom 23. November 2011 hiess das Handelsgericht des Kantons Zürich die Klage gut und erklärte die schweizerischen Formmarken Nr. 411 469, 433 265, 433 266, 433 267 und 433 268 für nichtig.
Es hielt unter anderem fest, jede Abweichung von der Geometrie des gefüllten Zylinders führe zu Nachteilen in Form höherer Kosten, was sich besonders bei den Werkzeugkosten zeige, die gemäss Gutachten bei den kompatiblen Alternativen 11,06 - 30,91 % und bei den nicht kompatiblen 28.8 - 54.13 % höher lägen als bei den Werkzeugen für den LEGO-Stein. Den Einwand der Beklagten, die Werkzeugkosten fielen nicht ins Gewicht, weil sie sich auf die Gesamtkosten für die Herstellung von 5 Mio. Bausteinen letztlich nicht massgeblich auswirkten, erachtete das Handelsgericht als unzutreffend. Ein Hersteller könne sich nicht mit der Aussicht begnügen, die Kosten seines Werkzeugs auf 5 Mio. damit zu produzierende Steine umlegen zu können; vielmehr müsse er die Initialkosten aufbringen, die erforderlich seien, um nicht nur mehrere Werkzeuge pro Steinform, sondern auch Werkzeuge im Hinblick auf ganz verschiedene Steinformen für ein ganzes Sortiment herstellen zu lassen. Bei Kosten eines einzelnen Werkzeugs von über Fr. 80'000.-- bis über Fr. 115'000.-- ergäben die von den Experten ermittelten Differenzen auch im allergünstigsten Fall (11,06 %) Summen, die sich durchaus massgeblich auswirkten. Damit erwiesen sich alle Alternativformen als jedenfalls anfänglich wesentlich teurer als der LEGO-Stein, weshalb sie das Kriterium, dass sie nicht mit höheren Herstellungskosten verbundene Ausführungen darstellen als der LEGO-Stein, nicht erfüllten.
Das Handelsgericht erwog im Weiteren, alle Alternativen erwiesen sich auch insgesamt, d.h. über die Lebensdauer des Werkzeugs, als teurer. Bei den kompatiblen Alternativen seien die Mehrkosten für die Herstellung gegenüber dem LEGO-Stein gemäss Gutachten mit 1.326 - 4.927 % zu beziffern. Diese von den Experten ermittelten Differenzen seien unter Berücksichtigung der Aussagen des ehemaligen Entwicklungsleiters der Beklagten, wonach jede Ersparnis bei der Produktion wichtig sei, durchaus relevant, womit die kompatiblen Alternativen das Kriterium, dass sie nicht mit höheren Herstellungskosten verbunden sein dürfen, nicht erfüllten. Bei den nicht kompatiblen Alternativen lägen die Herstellungskosten pro Teil etwa 50 % über den Kosten für den LEGO-Stein.
Damit scheiterten alle Alternativformen am Kostenkriterium, womit die von den Streitmarken beanspruchten Formen als technisch notwendig im Sinne von <ref-law> zu betrachten seien, was zur Nichtigerklärung der Streitmarken führe.
C. Mit Beschwerde in Zivilsachen beantragt die Beklagte dem Bundesgericht, es sei das Urteil des Handelsgerichts des Kantons Zürich vom 23. November 2011 aufzuheben und es sei die Nichtigkeitsklage abzuweisen. Eventualiter sei das angefochtene Urteil aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.
Die Beschwerdeführerin reichte dem Bundesgericht eine Replik, die Beschwerdegegnerin eine Duplik ein.

Erwägungen:
1. 1.1 Der angefochtene Entscheid ist in einer zivilrechtlichen Streitigkeit (<ref-law>) im Zusammenhang mit geistigem Eigentum ergangen, für die ein Bundesgesetz (<ref-law>) eine einzige kantonale Instanz vorsieht (Art. 74 Abs. 2 lit. b und Art. 75 Abs. 2 lit. a BGG). Die Beschwerdeführerin ist mit ihren Anträgen vor der Vorinstanz unterlegen (<ref-law>) und der angefochtene Entscheid schliesst das Verfahren ab (<ref-law>). Auf die Beschwerde, die unter Einhaltung der gesetzlichen Frist (<ref-law>) und Form (<ref-law>) erhoben wurde, kann daher grundsätzlich eingetreten werden.
1.2 Mit der Beschwerde in Zivilsachen kann die Verletzung von Bundesrecht (einschliesslich Bundesverfassungsrecht) gerügt werden (<ref-law>; <ref-ruling> E. 1.2). Nicht zu den in <ref-law> vorgesehenen Rügegründen gehört hingegen die Verletzung kantonaler Verfahrensvorschriften, deren Anwendung und Auslegung vom Bundesgericht einzig unter dem Blickwinkel eines Verstosses gegen Bundesrecht bzw. gegen Bundesverfassungsrecht beurteilt werden kann (<ref-ruling> E. 2.4; <ref-ruling> E. 4.3 S. 521; <ref-ruling> E. 1.2 S. 382 f.). Auf das Verfahren vor der Vorinstanz fand noch die nunmehr aufgehobene Zivilprozessordnung des Kantons Zürich vom 13. Juni 1976 (aZPO/ZH) Anwendung (vgl. Art. 404 Abs. 1 der Schweizerischen Zivilprozessordnung [ZPO; SR 272]).
Weist das Bundesgericht eine Streitsache an die Vorinstanz zurück, hat die mit der Neubeurteilung befasste kantonale Instanz die rechtliche Beurteilung, mit der die Rückweisung begründet wurde, ihrer Entscheidung zugrunde zu legen. Diese Beurteilung bindet auch das Bundesgericht. Wegen dieser Bindung der Gerichte ist es ihnen wie auch den Parteien, abgesehen von allenfalls zulässigen Noven, verwehrt, der Beurteilung des Rechtsstreits einen anderen als den bisherigen Sachverhalt zu unterstellen oder die Sache unter rechtlichen Gesichtspunkten zu prüfen, die im Rückweisungsentscheid ausdrücklich abgelehnt oder überhaupt nicht in Erwägung gezogen worden sind. Der Umfang der Bindung ergibt sich aus der Begründung der Rückweisung, die sowohl den Rahmen für die neuen Tatsachenfeststellungen als jenen für die neue rechtliche Begründung vorgibt. Die vom Bundesgericht bereits entschiedenen Fragen sind jedenfalls nicht mehr zu überprüfen (<ref-ruling> E. 2 S. 335 f. mit Hinweisen).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Mit Blick auf die Begründungspflicht des Beschwerdeführers (Art. 42 Abs. 1 und 2 BGG) behandelt es aber grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind; es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2.2.1; <ref-ruling> E. 1.4.1; je mit Hinweisen). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>). Macht der Beschwerdeführer beispielsweise eine Verletzung des Willkürverbots (<ref-law>) geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich; er hat vielmehr im Einzelnen zu zeigen, inwiefern der angefochtene Entscheid offensichtlich unhaltbar ist (<ref-ruling> E. 3 S. 352; <ref-ruling> E. 5.5 S. 5; <ref-ruling> E. 3.2 S. 444).
Unerlässlich ist im Hinblick auf Art. 42 Abs. 2 sowie <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Rechtsverletzung liegt. Der Beschwerdeführer soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die er im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit seiner Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2.1 S. 245 f.; <ref-ruling> E. 2a S. 400; <ref-ruling> E. 3 S. 749). Die Begründung hat ferner in der Beschwerdeschrift selbst zu erfolgen und der blosse Verweis auf Ausführungen in anderen Rechtsschriften oder auf die Akten reicht nicht aus (<ref-ruling> E. 3.1 S. 399 f.; <ref-ruling> E. 2.3 S. 387 f.; je mit Hinweisen).
1.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substantiiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss <ref-law> gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre; andernfalls kann ein Sachverhalt, der vom im angefochtenen Entscheid festgestellten abweicht, nicht berücksichtigt werden. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3 S. 351 f., 393 E. 7.1 S. 398, 462 E. 2.4 S. 466 f.).
2. Die Beschwerdeführerin wirft der Vorinstanz zunächst eine unzutreffende Verteilung der Beweislast hinsichtlich der technischen Notwendigkeit (<ref-law>) vor.
Die Vorinstanz hat es in Würdigung eines mit grossem Aufwand erstellten Gutachtens als erwiesen erachtet, dass sämtliche Alternativformen mit höheren Herstellungskosten verbunden sind als der LEGO-Baustein und hat daher die von den Streitmarken beanspruchten Formen als technisch notwendig im Sinne von <ref-law> beurteilt. Wo das Gericht in Würdigung von Beweisen zur Überzeugung gelangt, eine Tatsachenbehauptung sei bewiesen oder widerlegt, ist die Beweislastverteilung gegenstandslos und liegt Beweiswürdigung vor (<ref-ruling> E. 5.4 S. 601 f. mit Hinweisen). Die unter Berufung auf Art. 8 und 9 ZGB erhobenen Vorbringen der Beschwerdeführerin zur Beweislastverteilung stossen demnach ins Leere.
Entgegen der in der Beschwerde vertretenen Ansicht lässt sich auch aus dem Umstand, dass die Beschwerdegegnerin keine Kaution für das erstellte Gutachten leistete, nicht ableiten, diese hätte auf den Beweis hinsichtlich der technischen Notwendigkeit verzichtet. Nachdem die Vorinstanz gestützt auf das gerichtliche Gutachten die tatsächlichen Voraussetzungen für den absoluten Ausschlussgrund der technischen Notwendigkeit der beanspruchten Formen für erwiesen erachtet hat, ist die von der Beschwerdeführerin ins Feld geführte Beweislastverteilung auch in diesem Zusammenhang unerheblich. Inwiefern das prozessuale Verhalten der Gegenpartei im Rahmen der Beweiswürdigung zu berücksichtigen war, richtete sich im vorinstanzlichen Verfahren im Übrigen nach dem kantonalen Verfahrensrecht. Die Schlüsse, die das kantonale Gericht in tatsächlicher Hinsicht aus Beweisen und konkreten Umständen zieht, sind im Beschwerdeverfahren lediglich hinsichtlich ihrer Verfassungsmässigkeit überprüfbar; eine Verletzung verfassungsmässiger Rechte zeigt die Beschwerdeführerin diesbezüglich allerdings nicht auf.
3. Die Beschwerdeführerin rügt, die von der Vorinstanz festgestellten Mehrkosten für die Herstellung von Alternativformen seien nicht bedeutsam genug, um die beanspruchten Formen als technisch notwendig (<ref-law>) erscheinen zu lassen.
3.1 Das Bundesgericht hielt in seinem Rückweisungsentscheid fest, die tatsächlichen Feststellungen im angefochtenen Urteil des Handelsgerichts erlaubten die Beurteilung nicht, ob die auf den bestimmt proportionierten Quadern aufgesetzten, in bestimmter Weise angeordneten zylinderförmigen Noppen zur Erreichung der angestrebten Klemm- oder Stabilisierungswirkung beim Zusammenbau der Spielbausteine technisch notwendig sind. Dies wäre nach dem Rückweisungsentscheid der Fall, wenn Mitbewerbern wie der Beschwerdegegnerin mit dem Verbot ihrer Verwendung der Verzicht auf eine naheliegende und zweckmässige Form zugemutet würde, so dass sie an deren Stelle eine weniger praktische, eine weniger solide oder eine mit grösseren Herstellungskosten verbundene Ausführung wählen müssten (<ref-ruling> E. 3.2.4 S. 524).
Damit hat das Bundesgericht die Kriterien, unter denen mögliche Alternativformen als unzumutbar zu erachten sind und demzufolge die als Marke beanspruchte Form als technisch notwendig im Sinne von <ref-law> zu gelten hat, für die Vorinstanz grundsätzlich verbindlich umschrieben. Dabei hat es nicht etwa erwogen, allfällig festzustellende Mehrkosten bei der Herstellung von Alternativformen seien zusätzlich auf ihre Zumutbarkeit für Mitbewerber zu überprüfen, geschweige denn, Mehrkosten von 5 % seien generell als zumutbar zu erachten, wie dies die Beschwerdeführerin anzunehmen scheint. Entsprechend stellte das Bundesgericht auch in seinem Erläuterungsurteil fest, die angeordnete Rückweisung sei allein zur tatsächlichen Feststellung erfolgt, ob die nach dem handelsgerichtlichen Urteil vom 17. Dezember 2002 bestehenden praktikablen Alternativen zu runden, gefüllten Noppen ebenso praktisch, ebenso solide und mit keinen grösseren Herstellungskosten verbunden seien als die umstrittene, als Marke beanspruchte Form der auf dem Quader aufgesetzten Noppen (Urteil 4C.86/2004 vom 7. Juli 2004 E. 2.1.1 mit Verweis auf <ref-ruling> E. 3.2.4 S. 524).
3.2 Im Übrigen rechtfertigt sich bei der Beurteilung der Zumutbarkeit möglicher Alternativformen im Hinblick auf die wettbewerbliche Gleichbehandlung die Anwendung eines strengen Prüfungsmassstabs. Die mit der Einräumung einer Formmarke verbundene, zeitlich unbeschränkte Monopolstellung des Markeninhabers soll nach <ref-law> nur ermöglicht werden, sofern den Mitbewerbern dadurch angesichts vorhandener gleichwertiger Alternativen kein Nachteil entsteht. Ist die Herstellung alternativer Formen mit Mehrkosten verbunden, so führt dies auch dann zur Unzumutbarkeit der entsprechenden Wahl einer anderen Warenform, wenn der feststellbare Unterschied gering ausfällt. Im Sinne der Gleichbehandlung im funktionierenden Wettbewerb ist den Konkurrenten eine gleichwertige Ausgangslage zu erhalten (vgl. PHILIPPE GILLIÉRON, Les divers régimes de protection des signes distinctifs et leur rapport avec le droit des marques, 2000, S. 229; EUGEN MARBACH, Markenrecht, in: Schweizerisches Immaterialgüter- und Wettbewerbsrecht [SIWR], Bd. III/1, 2. Aufl. 2009, Rz. 527).
Lassen sich - wie vorliegend aufgrund einer Gerichtsexpertise - bei Alternativformen höhere Herstellungskosten feststellen, so ist diese Gleichbehandlung nicht gewährleistet und es ist für die Prüfung der technischen Notwendigkeit (<ref-law>) davon auszugehen, dass der Kostenunterschied geeignet ist, sich im Wettbewerb auszuwirken. Die festgestellten Kostenunterschiede im Sinne einer weiteren materiellen Voraussetzung zusätzlich noch darauf zu prüfen, ob sich diese unter Berücksichtigung des konkreten Konkurrenzverhältnisses, der erzielten Umsätze und Gewinnmargen dem Konkurrenten zumuten lassen (vgl. etwa den von der Beschwerdeführerin zitierten <ref-ruling> E. 3c S. 159), erscheint nicht nur unter dem Gesichtspunkt der Gleichbehandlung im Wettbewerb fragwürdig, sondern würde auch zu erheblicher Rechtsunsicherheit führen und wäre kaum justiziabel (vgl. bereits ALOIS TROLLER, Immaterialgüterrecht, Bd. I, 3. Aufl. 1983, S. 441 f.). Entsprechend wurde im Rückweisungsentscheid auch vorgegeben, bei der Beurteilung der Zumutbarkeit bzw. Unzumutbarkeit von Alternativformen neben weiteren Kriterien darauf abzustellen, ob diese mit grösseren Herstellungskosten verbunden sind, und nicht etwa auf weitere Kosten (für Verpackung, Vertrieb etc.) oder auf Gewinnmargen unter Berücksichtigung von Endverkaufspreisen, auf die sich die Berechnungen in der Beschwerde stützen.
Der Beschwerdeführerin kann demnach nicht gefolgt werden, wenn sie vorbringt, die gestützt auf das gerichtliche Gutachten festgestellten höheren Herstellungskosten für alternative Lösungen von 1.326 - 4.927 % gegenüber dem LEGO-Stein seien bundesrechtlich unerheblich. Der Vorinstanz ist keine Verletzung von <ref-law> vorzuwerfen. Es braucht daher nicht auf die Ausführungen der Beschwerdeführerin zur vorinstanzlichen Alternativbegründung eingegangen zu werden, wonach bereits der Umstand der höheren Werkzeugkosten zur Gutheissung der Nichtigkeitsklage führe.
4. Die Beschwerdeführerin bringt weiter vor, die tatsächlichen Herstellungskosten der Alternativbausteine seien ohnehin tiefer als im angefochtenen Entscheid festgestellt. Sie wirft der Vorinstanz diesbezüglich Willkür (<ref-law>) und eine Verletzung des rechtlichen Gehörs (<ref-law>) vor.
4.1 Sie behauptet, die Berechnungen der Experten basierten auf unrealistisch engen Toleranzen und auf falschen Prämissen betreffend Massgenauigkeit der Werkzeuge sowie Masskontrolle der Formteile. Höhere Toleranzen führten zu tieferen Werkzeug- und Herstellungskosten; entgegen den Experten entstünden bei den Alternativformen sodann keine höheren Wartungskosten. Die Herstellungskosten für kompatible Alternativbausteine seien unter Berücksichtigung dieser Aspekte teilweise tiefer zu veranschlagen als diejenige des LEGO-Grundbausteins.
4.1 Sie behauptet, die Berechnungen der Experten basierten auf unrealistisch engen Toleranzen und auf falschen Prämissen betreffend Massgenauigkeit der Werkzeuge sowie Masskontrolle der Formteile. Höhere Toleranzen führten zu tieferen Werkzeug- und Herstellungskosten; entgegen den Experten entstünden bei den Alternativformen sodann keine höheren Wartungskosten. Die Herstellungskosten für kompatible Alternativbausteine seien unter Berücksichtigung dieser Aspekte teilweise tiefer zu veranschlagen als diejenige des LEGO-Grundbausteins.
4.2 4.2.1 Die Vorbringen zu den vorinstanzlich gestützt auf das gerichtliche Gutachten festgestellten Herstellungskosten sind über weite Strecken appellatorisch. Die Beschwerdeführerin zeigt mit ihren Ausführungen keine Willkür (<ref-law>) auf, sondern kritisiert in unzulässiger Weise und unter mehrseitiger Wiederholung ihrer Vorbringen im kantonalen Verfahren das Beweisergebnis der Vorinstanz. Dabei beruft sie sich teilweise auf tatsächliche Vorbringen, die sich nicht auf die Sachverhaltsfeststellungen im angefochtenen Entscheid stützen lassen (vgl. <ref-law>), wie etwa die Behauptungen, die Experten hätten die Toleranzen der Werkzeuge für die Produktion im KATZ im Rahmen ihrer Expertise bestimmen können oder die Gutachter hätten die Bausteine der Parteien messen und daraus Rückschlüsse auf "realistische" Toleranzen machen können. Damit ist sie nicht zu hören.
4.2.2 Die Beschwerdeführerin zeigt auch keine Verletzung des Gehörsanspruchs (<ref-law>) auf, wenn sie im Zusammenhang mit den angeblich falschen Prämissen betreffend Massgenauigkeit der Werkzeuge und Masskontrolle der Formteile sowie den Aspekt der Wartungskosten lediglich seitenweise wortwörtlich aus ihren Eingaben im kantonalen Verfahren zitiert und behauptet, die Vorinstanz habe sich damit nicht auseinandergesetzt. Ebenso wenig vermag sie eine Gehörsverletzung darzutun, indem sie ohne weitere Ausführungen vorbringt, die Vorinstanz habe bestimmte Ergänzungsfragen nicht zugelassen, ohne dies zu begründen.
Der Anspruch auf rechtliches Gehör (<ref-law>) verlangt insbesondere, dass das Gericht die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt (<ref-ruling> E. 4.1 S. 88 mit Hinweisen). Daraus folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen. Die Begründung muss kurz die Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die sich sein Entscheid stützt (<ref-ruling> E. 2.4 S. 72). Nicht erforderlich ist hingegen, dass sich der Entscheid mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Es genügt, wenn der Entscheid gegebenenfalls sachgerecht angefochten werden kann (<ref-ruling> E. 4.2 S. 355; <ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 3.3 S. 445; je mit Hinweisen).
Der Anspruch auf rechtliches Gehör (<ref-law>) verlangt insbesondere, dass das Gericht die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt (<ref-ruling> E. 4.1 S. 88 mit Hinweisen). Daraus folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen. Die Begründung muss kurz die Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die sich sein Entscheid stützt (<ref-ruling> E. 2.4 S. 72). Nicht erforderlich ist hingegen, dass sich der Entscheid mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Es genügt, wenn der Entscheid gegebenenfalls sachgerecht angefochten werden kann (<ref-ruling> E. 4.2 S. 355; <ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 3.3 S. 445; je mit Hinweisen).
4.3 4.3.1 Die Beschwerdeführerin zeigt hinsichtlich der von den Experten angenommenen Toleranzen von +/- 5? keine Willkür auf, wenn sie dem angefochtenen Entscheid ihre eigene Ansicht zu den zu verwendenden Toleranzen gegenüberstellt und behauptet, die Annahme der Experten im Rahmen des Gutachtens sei viel zu eng und wirklichkeitsfremd, was sich auf die Berechnung der Herstellungskosten ausgewirkt habe. Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst, wenn sie 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.). Mit den blossen Vorbringen, es habe sich eine Offerte eines Dritten vom 5. Oktober 2005 für die Herstellung entsprechender Werkzeuge bei den Akten befunden, die sich bei den Noppen auf Toleranzen von +/- 20? beziehe bzw. sie selber verwende Toleranzen von mindestens +/- 10? weist sie die im gerichtlichen Gutachten verwendeten Toleranzen nicht als willkürlich aus. Entsprechendes gilt für die Behauptung, es sei bei den Toleranzen auf die am KATZ produzierten Bausteine und nicht diejenigen der im Handel erhältlichen "echten" LEGO-Bausteine abzustellen.
Abgesehen davon legt die Beschwerdeführerin auch nicht dar, wie sich die angeblich realitätsfremden Toleranzen konkret auf den Vergleich der Herstellungskosten ausgewirkt und damit zu einem unhaltbaren Ergebnis geführt haben sollen, zumal im Rahmen der gutachterlichen Versuche auch für die LEGO-Bausteine dieselben Werte verwendet wurden (vgl. <ref-ruling> E. 2.4; <ref-ruling> E. 2.2.2. S. 318 f.; <ref-ruling> E. 1.3 S. 4 f.; je mit Hinweisen).
4.3.2 Soweit die Beschwerdeführerin der Vorinstanz im Zusammenhang mit den konkret verwendeten Toleranzen eine Verletzung des rechtlichen Gehörs vorwirft, sind ihre Vorbringen unbegründet. Die Parteien haben sich über den Versuchsablauf geeinigt, den sie im weiteren Verlauf auch eng begleiteten. Die Beschwerdeführerin behauptet vor Bundesgericht nicht, sie hätte sich bereits im Hauptverfahren darauf berufen, dass sie bei ihren eigenen Bausteinen Toleranzen von mindestens +/- 10? verwende bzw. dass diese bei Spielbausteinen üblich seien. Vielmehr trägt sie lediglich vor, dies in ihrer Stellungnahme vom 22. Oktober 2010 zum Beweisergebnis (act. 463) vorgebracht zu haben. Wie die Beschwerdegegnerin zutreffend einwendet, kann demnach hinsichtlich der Toleranzen nicht von Beweislosigkeit gesprochen werden. Ebenso wenig kann die Darstellung des von der Vorinstanz als widersprüchlich erachteten Prozessverhaltens im angefochtenen Entscheid als aktenwidrig bezeichnet werden.
Die Beschwerdeführerin wurde vom Gericht auf Mitteilung des Gutachters Prof. A._ vom 9. April 2009 hin eigens dazu aufgefordert, nähere Angaben betreffend vorgeschriebene Masse und Toleranzen zu machen. Sie verweigerte jedoch unter Berufung auf das Betriebsgeheimnis ausdrücklich jegliche Angaben. Die Beschwerdeführerin versucht vor Bundesgericht vergeblich, die damalige Bedeutung der vom Gutachter verlangten Angaben unter Hinweis auf die Wortwahl des Schreibens (wonach diesbezügliche Angaben "hilfreich" wären) und den angeblichen Umstand zu entkräften, die Angaben seien auf den Aspekt der Nachschwindung beschränkt gewesen. Zum einen gilt es zu berücksichtigen, dass das Schreiben von Prof. A._ vom 9. April 2009 formell an die Vorinstanz gerichtet und entsprechend abgefasst war, zumal entsprechende Informationen von den Gutachtern nicht direkt bei den Parteien verlangt werden konnten, sondern das Gericht die verfahrensleitenden Verfügungen zu treffen hatte; zum anderen geht aus der gutachterlichen Anfrage ohne Weiteres erkennbar hervor, dass die verlangten Angaben zu den Toleranzen nicht nur für die Funktionskontrolle des Werkzeugs, sondern auch für die Überprüfung der Massgenauigkeit der im Rahmen des Versuchsablaufs produzierten Bausteine von Bedeutung waren. Dennoch lehnte es die Beschwerdeführerin in ihrem Schreiben vom 5. Mai 2009 unter Berufung auf die Geheimhaltung kategorisch ab, Angaben zu den Toleranzen zu machen. Der Vorinstanz ist keine Bundesrechtsverletzung vorzuwerfen, wenn sie unter diesen Umständen die erst anlässlich der Stellungnahme vom 22. Oktober 2010 zum Beweisergebnis erhobenen Vorbringen der Beschwerdeführerin, sie arbeite mit Toleranzen von +/- 10?, die bei Noppen üblich seien, als widersprüchlich und unter dem Gesichtspunkt von Treu und Glauben unzulässig erachtete und auf das ebenfalls erst in diesem Verfahrensstadium beantragte Gutachten bezüglich Toleranzen verzichtete.
Die Rüge der Gehörsverletzung stösst auch im Zusammenhang mit der Urteilsbegründung hinsichtlich der im Gutachten tatsächlich verwendeten Toleranzen ins Leere. Insbesondere vermag die Beschwerdeführerin nicht aufzuzeigen, inwiefern ihr die Begründung des angefochtenen Entscheids verunmöglicht hätte, diesen gegebenenfalls sachgerecht anzufechten (<ref-ruling> E. 4.2 S. 355; <ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 3.3 S. 445; je mit Hinweisen).
Die Beschwerdeführerin vermag weder eine verfassungswidrige Anwendung kantonaler Verfahrensvorschriften noch eine Gehörsverletzung darzutun.
5. Die Begründung der Vorinstanz, wonach die von den Streitmarken beanspruchten Formen aufgrund der höheren Herstellungskosten für Alternativformen als technisch notwendig (<ref-law>) zu erachten sind, hält vor Bundesgericht stand. Auf die Ausführungen der Beschwerdeführerin zum weiteren Kriterium der Praktikabilität von Alternativlösungen ist daher nicht weiter einzugehen.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 15'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 17'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 3. Juli 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann