3. Die Beschwerdeführerin rügt eine bundesrechtswidrige Einschränkung ihres Feststellungsinteresses durch die Vorinstanz.

3.1 Wer ein rechtliches Interesse nachweist, kann nach Art. 52 MSchG (SR 232.11) vom Richter feststellen lassen, dass ein Recht oder ein Rechtsverhältnis nach diesem Gesetz besteht oder nicht besteht. Diese markenrechtliche Feststellungsklage erlaubt in der Form der Löschungs- oder Nichtigkeitsklage die Nichtigerklärung und Löschung einer Marke aus dem Markenregister. Das Rechtsschutzinteresse muss erheblich sein (BGE 120 II 144 E. 2a; Urteile 4A_324/2009 vom 8. Oktober 2009 E. 2; 4C.369/2004 vom 25. Januar 2005 E. 2.3, in: sic! 2005 S. 682; LUCAS DAVID, Markenschutzgesetz, Muster- und Modellgesetz, 2. Aufl. 1999, N. 9 zu Art. 52 MSchG; CHRISTOPH WILLI, Markenschutzgesetz, MSchG, 2002, N. 6 zu Art. 52 MSchG). Wann ein solches Interesse gegeben ist, bestimmt das Bundesrecht (BGE 135 III 378 E. 2.2 S. 379 f. mit Hinweisen). Ein Feststellungsinteresse liegt vor, wenn die Rechtsbeziehungen der Parteien ungewiss sind, die Ungewissheit durch die Feststellung über Bestand und Inhalt des Rechtsverhältnisses beseitigt werden kann und ihre Fortdauer der Klagepartei nicht zugemutet werden kann, weil sie sie in ihrer Bewegungsfreiheit behindert (BGE 135 III 378 E. 2.2 S. 380; BGE 123 III 414 E. 7b S. 429; BGE 120 II 144 E. 2; je mit Hinweisen).

3.2 Die Vorinstanz erwog, die Beschwerdegegnerin habe Widersprüche gegen die beiden Marken der Beschwerdeführerin eingereicht. Zudem verwende die Beschwerdeführerin ihre allenfalls mit der Marke "Yello" verwechselbare Marke "Yallo" im Geschäftsverkehr. Diese habe somit grundsätzlich ein rechtlich geschütztes Interesse an der Nichtigerklärung der Marken der Beschwerdegegnerin bzw. an den Eventualbegehren. Die Marken CH-Nrn. 535 045 und 537 384 der Beschwerdeführerin seien für die Klassen 9, 16, 35, 36, 38 und 42 registriert. Die Beschwerdeführerin habe somit lediglich insoweit ein Rechtsschutzinteresse an der Nichtigerklärung der Marken der Beschwerdegegnerin, als diese für die gleichen Klassen registriert seien. Anderes bringe die Beschwerdeführerin denn auch nicht vor. Sie trat daher auf die Klage insoweit nicht ein, als die Marken der Beschwerdegegnerin für andere Klassen registriert sind als diejenigen, für welche die Marken der Beschwerdeführerin eingetragen sind.

3.3 Umstritten ist demnach nicht das Bestehen eines Feststellungsinteresses an sich, sondern dessen Reichweite bzw. Umfang. Die Beschwerdeführerin ist der Auffassung, ihr Rechtsschutzinteresse richte sich auf die Nichtigerklärung der gesamten Marken der Beschwerdegegnerin, soweit diese mit einem Nichtigkeitsgrund behaftet seien. Sie habe die Nichtigerklärung der Marken der Beschwerdegegnerin mit dem Nichtgebrauch derselben begründet. Die Berufung auf Nichtgebrauch setze aber kein besonderes Interesse voraus. Eine Beschränkung des schutzwürdigen Interesses könnte sich jedenfalls nicht nach Waren- oder Dienstleistungsklassen richten. Zudem habe sie die Nichtigkeit der angefochtenen Marken auch mit der fehlenden Gebrauchsabsicht und der Rechtsmissbräuchlichkeit der Markenhinterlegung begründet. Auch in diesem Fall sei es nicht zweckmässig, das Feststellungsinteresse auf bestimmte Waren und Dienstleistungen zu beschränken, da die angefochtenen Marken im ganzen Umfang, in dem sich der Nichtigkeitsgrund als gegeben erweist, nichtig zu erklären seien, wie die bundesgerichtliche Rechtsprechung zeige.

Diese Argumentation ist zutreffend:

3.4 Zur Geltendmachung des Nichtgebrauchs einer Marke im Sinne von Art. 12 MSchG ist grundsätzlich jedermann befugt; ein spezieller Interessennachweis ist nicht erforderlich, da das allgemeine Interesse, bei der freien Zeichenbildung nicht durch zufolge Nichtgebrauchs ungültige Marken behindert zu werden, in der Regel genügt. Ausnahmsweise kann ein Rechtsschutzinteresse an der Nichtigerklärung jedoch dann fehlen, wenn die Opponentin das fragliche Zeichen oder ein diesem ähnliches Zeichen schon aus anderen Gründen selbst gar nicht benutzen kann oder benutzen darf, so dass für sie die Markeneintragung von vornherein keine weitere Behinderung in der freien Zeichenbildung bewirken kann. In einem solchen Fall kann der Nichtgebrauch nur geltend gemacht werden, wenn die Opponentin aufgrund besonderer Umstände dennoch ein schutzwürdiges Interesse daran hat, ein Wiederaufleben des zufolge Nichtgebrauchs untergegangenen Markenrechts zu verhindern (BGE 125 III 193 E. 2a S. 206; so auch WILLI, a.a.O., N. 6 zu Art. 52 MSchG; EUGEN MARBACH, Markenrecht, SIWR, Bd. III/1, 2. Aufl. 2009, S. 418 f. Rz. 1418; KARIN BÜRGI LOCATELLI, Der rechtserhaltende Markengebrauch in der Schweiz, 2008, S. 202; enger DAVID, der ein schutzwürdiges Interesse demjenigen abspricht, der die angefochtene Marke tatsächlich nicht gebrauchen kann, weil er sich gar nicht mit Waren und Dienstleistungen befasst, für welche die angeblich ungebrauchte Marke beansprucht wird: DAVID, a.a.O., N. 14 zu Art. 12 MSchG und N. 9 zu Art. 52 MSchG; derselbe, Bemerkungen zu BGE 125 III 193, AJP 1999 S. 1483 ff., 1487).

Wie die Beschwerdeführerin zutreffend vorbringt, kann es bezüglich der Anforderungen an das Rechtsschutzinteresse keinen Unterschied machen, ob der Nichtgebrauch einer Marke ausserprozessual geltend gemacht oder im Rahmen einer Nichtigkeitsklage nach Art. 52 MSchG angerufen wird. Es macht keinen Sinn, das Interesse an der gerichtlichen Geltendmachung des Nichtgebrauchs enger zu fassen als dasjenige an der ausserprozessualen Geltendmachung. Eine solche Differenzierung geht denn auch aus BGE 125 III 193 E. 2a S. 206 nicht hervor. Es gelten stets die gleichen, relativ geringen Voraussetzungen.

Nach dem Gesagten musste die Beschwerdeführerin kein spezielles Interesse nachweisen. Sie kann sich grundsätzlich auf ihr allgemeines Interesse stützen, bei der freien Zeichenbildung nicht durch die von der Beschwerdegegnerin eingetragenen, angeblich nicht gebrauchten Marken behindert zu werden. Gründe, aus denen die Beschwerdeführerin das fragliche Zeichen für die strittigen Waren oder Dienstleistungen nicht benutzen darf oder kann, sind keine festgestellt. Die Vorinstanz hätte daher das Rechtsschutzinteresse der Beschwerdeführerin nicht von vornherein auf den Schutzbereich deren eigener Marken beschränken dürfen.

Dies gilt umso mehr, als die Beschwerdeführerin ihre Klage auf Nichtigerklärung der Marken der Beschwerdegegnerin auch mit der fehlenden Gebrauchsabsicht bzw. Rechtsmissbräuchlichkeit der Hinterlegung (Defensivmarken) begründet hat. Der Richter erklärt die angefochtene Marke in dem Umfang für nichtig, in dem sich der geltend gemachte Nichtigkeitsgrund als begründet erweist. Eine Beschränkung der Nichtigerklärung der angefochtenen Marke auf die "gleichen Klassen", für welche die Marke des Opponenten eingetragen ist, worauf die Erwägungen der Vorinstanz hinauslaufen, findet nicht statt. Vielmehr beschlägt die Nichtigerklärung bei Bejahung des angerufenen Nichtigkeitsgrundes die angefochtene Marke im gesamten betroffenen Umfang (vgl. z.B. Urteile 4C.431/2004 vom 2. März 2005, in: sic! 2005 S. 463 ff.; 4C.82/2007 vom 30. Mai 2008, teilw. publ. in: sic! 2008 S. 732 ff.; vgl. auch BGE 127 III 160 E. 1a S. 163 f.). Um ein solches Urteil zu ermöglichen, muss im selben Umfang auch das Rechtsschutzinteresse, sofern es grundsätzlich gegeben ist, an einer entsprechenden Nichtigkeitsklage bejaht werden. Dies hat die Vorinstanz verkannt.

Hinzu kommt, dass es ohnehin nicht sachgerecht wäre, eine Einschränkung der Klagelegitimation nach Klassen gemäss dem Abkommen von Nizza über die internationale Klassifikation von Waren und Dienstleistungen für die Eintragung von Marken, revidiert in Stockholm am 14. Juli 1967 (SR 0.232.112.8), vorzunehmen, wie dies die Vorinstanz getan hat. Entscheidend könnte bei einer Einschränkung von vornherein nur der Gebrauch der Marke für gleichartige Waren oder Dienstleistungen sein. Für die Beurteilung der Gleichartigkeit der Waren oder Dienstleistungen ist indessen die Klasseneinteilung nach dem Nizza-Abkommen nicht vorbehaltlos ausschlaggebend (WILLI, a.a.O., N. 54 zu Art. 3 MSchG; BGE 96 II 257 E. 2 S. 260; Urteil 4A_103/2008 vom 7. Juli 2008 E. 8.2, in: sic! 2008 S. 907 ff.). Auch dies rügt die Beschwerdeführerin zu Recht.

3.5 Entgegen der Ansicht der Beschwerdegegnerin ändert nichts, dass nach den Erwägungen des Handelsgerichts (in seinem durch das Kassationsgericht aufgehobenen Urteil) die Beschwerdeführerin den Nichtgebrauch der Marken "Yello" der Beschwerdegegnerin nicht glaubhaft machen konnte, sondern vielmehr die Beschwerdegegnerin deren Gebrauch glaubhaft darlegte, weshalb das Handelsgericht auf die Vorbringen betreffend fehlende Gebrauchsabsicht und Defensivmarke nicht einging. Die Frage, ob ein geltend gemachter Nichtigkeitsgrund zutrifft oder nicht, beschlägt die materielle Beurteilung und ist für die Frage der Legitimation nicht ausschlaggebend.

3.6 Nichts Anderes ergibt sich sodann aus der von der Vorinstanz erwähnten Möglichkeit von Teilnichtigkeitsklagen. Wenn ein Nichtigkeitsgrund das Schutzrecht des Klägers bloss teilweise beschlägt, etwa weil die vom Inhaber der älteren Marke angefochtene jüngere Marke nur für einen Teil der Warenliste der älteren Marke täuschender Natur ist, so kann die Feststellung teilweiser Nichtigkeit verlangt werden bzw. der Richter kann von Amtes wegen auf blosse Teilnichtigkeit erkennen (DAVID, a.a.O., N. 4 zu Art. 52 MSchG; VON BÜREN/MARBACH/DUCREY, Immaterialgüter- und Wettbewerbsrecht, 3. Aufl. 2008, S. 197 Rz. 932).

Eine solche Konstellation liegt in casu bezüglich der geltend gemachten Nichtigkeitsgründe des Nichtgebrauchs bzw. der fehlenden Gebrauchsabsicht nicht vor. Und betreffend die von der Beschwerdeführerin vor Handelsgericht eventuell beantragte negative Feststellung, dass ihre Marken bzw. der Domain-Namen "yallo.ch" die Marken der Beschwerdegegnerin nicht verletzen, spielt die Frage einer Teilnichtigkeit selbstredend keine Rolle.