Sachverhalt:
A. Mit Verfügung vom 5. Dezember 2000 stellte die Volkswirtschaftsdirektion des Kantons Zürich E._ als juristische Sekretärin im Amt für Wirtschaft und Arbeit (AWA) mit Antrittsdatum vom 16. März 2001 ein. Zu ihren Aufgaben gehörte die Beurteilung von Gesuchen um Arbeitsbewilligungen. Im Jahr 2006 wurde sie mit der Bearbeitung des Gesuchs um eine Arbeitsbewilligung für D._, welche für den damaligen Direktor H._ tätig sein sollte, betraut. Infolge verschiedener Differenzen mit ihren Vorgesetzten in Zusammenhang mit der Bearbeitung dieses Gesuchs resp. zweier Wiedererwägungsgesuche kündigte E._ das Arbeitsverhältnis mit Schreiben vom 16. Februar 2007 fristlos, welches sie am 22. Februar 2007 ihrem direkten Vorgesetzten übergab. Mit Entscheid vom 22. Februar 2007 verfügte die Anklagekammer des Obergerichts gestützt auf die von E._ in ihrer Strafanzeige vom 22. Dezember 2006 erhobenen Vorwürfe die Eröffnung eines Strafverfahrens gegen den Chef des AWA. Nachdem die Volkswirtschaftsdirektion am 27. Februar 2007 das Arbeitsverhältnis rückwirkend aufgelöst und sich infolge Unrechtmässigkeit der fristlosen Kündigung allfällige Forderungen vorbehalten hatte, verlangte E._ eine Begründung dieser Verfügung. Am 4. April 2007 erliess die Volkswirtschaftsdirektion eine praktisch identische Austrittsverfügung. Auf den von E._ dagegen eingereichten Rekurs trat der Regierungsrat mit Entscheid vom 19. August 2009 nicht ein.
B. E._ liess dagegen Beschwerde beim Verwaltungsgericht des Kantons Zürich führen. Dieses stellte in teilweiser Gutheissung der Beschwerde mit Entscheid vom 27. Januar 2010 fest, die fristlose Kündigung durch E._ sei gerechtfertigt gewesen, und verpflichtete den Kanton Zürich zur Leistung einer Entschädigung von drei Monatslöhnen sowie einer Abfindung von neun Monatslöhnen.
C. Der Kanton Zürich führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, es sei der vorinstanzliche Entscheid aufzuheben und festzustellen, die fristlose Kündigung von E._ sei nicht gerechtfertigt gewesen. Zudem ersucht der Kanton Zürich um Gewährung der aufschiebenden Wirkung seiner Beschwerde.
E._ lässt auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne, sowie auf Abweisung des Gesuchs um aufschiebende Wirkung schliessen.
D. Mit Verfügung vom 30. April 2010 wies das Bundesgericht das Gesuch um Gewährung der aufschiebenden Wirkung ab.

Erwägungen:
1. 1.1 Nach Art. 105 BGG legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Abs. 1). Es kann diese Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Abs. 2). Die Voraussetzungen für eine Sachverhaltsrüge nach Art. 97 Abs. 1 BGG und für eine Berichtigung des Sachverhalts von Amtes wegen nach Art. 105 Abs. 2 BGG stimmen im Wesentlichen überein. Soweit es um die Frage geht, ob der Sachverhalt willkürlich oder unter verfassungswidriger Verletzung einer kantonalen Verfahrensregel ermittelt worden ist, sind strenge Anforderungen an die Begründungspflicht der Beschwerde gerechtfertigt. Entsprechende Beanstandungen sind vergleichbar mit den in Art. 106 Abs. 2 BGG genannten Rügen. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Vielmehr ist in der Beschwerdeschrift nach den erwähnten gesetzlichen Erfordernissen darzulegen, inwiefern diese Feststellungen willkürlich bzw. unter Verletzung einer verfahrensrechtlichen Verfassungsvorschrift zustande gekommen sind. Andernfalls können Vorbringen mit Bezug auf einen Sachverhalt, der von den Feststellungen im angefochtenen Entscheid abweicht, nicht berücksichtigt werden. Vorbehalten bleiben offensichtliche Sachverhaltsmängel im Sinne von Art. 105 Abs. 2 BGG, die dem Richter geradezu in die Augen springen (<ref-ruling> E. 6.2 S. 288; <ref-ruling> E. 1.4.3 S. 255).
1.2 Am 14. Februar 2007 erhielt die Beschwerdegegnerin Kenntnis vom Schreiben des Direktors des Bundesamtes für Migration (BFM) vom 9. Februar 2007, in welchem dieser das Gesuch der Volkswirtschaftsdirektorin vom 22. Januar 2007 um Erteilung der Arbeitsbewilligung für D._ erneut ablehnte. Ihr Kündigungsschreiben vom 16. Februar 2007 übergab sie am 22. Februar 2007 ihrem direkten Vorgesetzten, dem stellvertretenden Amtschef. Am gleichen Tag entschied die Anklagekammer des Obergerichts, gestützt auf die Strafanzeige der Beschwerdegegnerin sei ein Strafverfahren gegen den Chef des AWA zu eröffnen.
Der Kanton Zürich macht unter Verweis auf den am 22. Februar 2007 ergangenen Entscheid der Eröffnung einer Strafuntersuchung eine offensichtlich unrichtige Feststellung des Sachverhalts geltend, da die Beschwerdegegnerin nach der Chronologie der Ereignisse anlässlich ihrer Kündigung von diesem Entscheid gar keine Kenntnis haben konnte.
Die Vorinstanz hat indessen gar nicht festgestellt, die Beschwerdegegnerin habe mit dem Entscheid zur Eröffnung einer Strafuntersuchung hinreichend Kenntnis allfälliger strafrechtlich relevanter Umstände gehabt. Vielmehr stellt sich die Vorinstanz auf den Standpunkt, die Beschwerdegegnerin habe davon ausgehen dürfen, dass allfällige strafrechtlich relevante Umstände gegeben seien, was durch den Entscheid der Eröffnung einer Strafuntersuchung bestätigt werde (Ziff. 18.3 des kantonalen Entscheids). Diese Feststellung ist weder offensichtlich unrichtig noch willkürlich.
2. 2.1 Rechtsverletzungen im Sinne von Art. 95 lit. a BGG prüft das Bundesgericht grundsätzlich frei, einschliesslich die Frage, ob die Auslegung und Anwendung des kantonalen Rechts zu einer Bundesrechtswidrigkeit führt respektive den Grundsatz der derogatorischen Kraft des Bundesrechts verletzt (Art. 49 Abs. 1 BV). Im Übrigen prüft das Bundesgericht die Handhabung des kantonalen Rechts - vorbehältlich der in Art. 95 lit. c und d BGG genannten Fälle - bloss auf Willkür hin (Art. 9 BV; vgl. Urteile 8C_953/2009 vom 23. Februar 2010 E. 3.2 und 8C_123/2009 vom 18. Januar 2010 E. 2, je mit Hinweisen).
Gemäss Art. 9 BV hat jede Person Anspruch darauf, von den staatlichen Organen ohne Willkür behandelt zu werden. Nach der Rechtsprechung ist eine Entscheidung willkürlich, wenn sie eine Norm oder einen klaren und unumstrittenen Rechtsgrundsatz offensichtlich schwer verletzt, sich mit sachlichen Gründen schlechthin nicht vertreten lässt 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. Willkürliche Rechtsanwendung liegt zudem nicht schon vor, wenn eine andere Lösung vertretbar oder sogar vorzuziehen wäre (<ref-ruling> E. 4.1 S. 133; <ref-ruling> E. 3.1 S. 153 mit Hinweisen).
Wird im Rahmen kantonalen öffentlichen Dienstrechts auf arbeitsvertragliche Bestimmungen des OR verwiesen, handelt es sich dabei ebenfalls um kantonales Recht (vgl. Urteile 1C_195/2007 vom 17. Dezember 2007 E. 4.1, 2C_492/2009 vom 18. August 2009 E. 2.2 oder 8C_952/2009 vom 18. Mai 2010 E. 1.2). Somit gilt für die gerügte Anwendung des kantonalen öffentlichen Personal- und Verfahrensrechts der Massstab der Willkür.
2.2 Der Kanton Zürich macht in verschiedener Hinsicht (Beweiswürdigung, Rechtsanwendung, Verhältnismässigkeit) eine Verletzung des Willkürverbots geltend.
2.2.1 Der Beschwerdeführer rügt, der vorinstanzliche Entscheid sei insoweit willkürlich, als damit ein Abweichen vom üblichen Vorgehen bei der Beurteilung von Arbeitsbewilligungen festgestellt worden sei.
Das BFM hatte das Gesuch um eine Arbeitsbewilligung bereits am 27. April 2006 erstmals abschlägig beurteilt. Es ist daher nicht ersichtlich, weshalb das AWA in der Folge keine verbindlichen Anordnungen hätte treffen können. Es finden sich in den Akten zudem hinreichend Anhaltspunkte dafür, dass den Vorgesetzten der Beschwerdegegnerin schon bald einmal bewusst war, dass das Gesuch abzulehnen war (vgl. insbesondere das Mail des stellvertretenden Chefs des AWA vom 18. April 2006). Das AWA hatte sich aber über den ersten abschlägigen Entscheid sowie auch über die erneute Ablehnung des BFM vom 8. Januar 2007 hinweggesetzt und seinerseits keine Verfügung erlassen; vielmehr gelangte die Volkswirtschaftsdirektorin mit Schreiben vom 22. Januar 2007 an den Direktor des BFM mit der Bitte um eine Ausnahmebewilligung. Dies wurde mit Schreiben vom 9. Februar 2007 unmissverständlich abgelehnt. Erst im Nachgang zu diesem dritten abschlägigen Entscheid des BFM und nach Verstreichen eines weiteren Monats leitete das AWA die von der Beschwerdegegnerin bereits im Herbst 2006 veranlassten Schritte ein. Bei diesem (an sich unbestrittenen) Verfahrensablauf (vgl. dazu einlässlich Ziff. 6 ff. des kantonalen Entscheids) durfte die Vorinstanz ihrerseits willkürfrei festhalten, dass "dem Vorgehen des AWA ... deshalb etwas Willkürliches" anhafte (Ziff. 16.1 des kantonalen Entscheids) bzw. sich das Vorgehen des Beschwerdeführers "zusammenfassend ... als bewusstes Abweichen von den üblicherweise für die Erteilung einer Arbeitsbewilligung notwendigen Voraussetzungen" erweise (Ziff. 16.4 des vorinstanzlichen Entscheids). Daran ändern auch die beiden Wiedererwägungsgesuche nichts, hat doch die Vorinstanz gestützt auf die Akten nachvollziehbar dargelegt, dass "zumindest einem Teil der Verantwortlichen der Volkswirtschaftsdirektion ... die illegale Anstellung D._s schon früh bewusst" war (Ziff. 12.2 des kantonalen Entscheids).
2.2.2 Die Vorinstanz erblickt einen wichtigen Grund für die fristlose Kündigung darin, dass der Kanton wiederholt vom üblichen Vorgehen bei der Beurteilung von Gesuchen um Arbeitsbewilligungen abgewichen sei. Von einem einmaligen Ausrutscher könne nicht gesprochen werden und für das gewählte Vorgehen sei kein öffentliches Interesse auszumachen. Der Kanton Zürich rügt, es habe sich dabei nur um ein einziges Verfahren gehandelt, was zur fristlosen Kündigung nicht habe Anlass geben können.
Die Vorgesetzten haben die Beschwerdegegnerin verschiedentlich desavouiert: So wurden die korrekte Ablehnung des ersten Wiedererwägungsgesuches durch die Beschwerdegegnerin sowie die von ihr erstatteten Meldungen bezüglich Schwarzarbeit an die zuständigen Stellen von der Assistentin des Amtschefs widerrufen. Das Dossier wurde der Beschwerdegegnerin entzogen und einer anderen Sachbearbeiterin zugeteilt mit der Weisung, die Arbeitsbewilligung zu erteilen, obwohl das BFM von Anfang an seine Zustimmung verweigerte und auch den Vorgesetzten bereits früh klar war, dass die gesetzlichen Voraussetzungen dafür nicht erfüllt waren. Schliesslich wandte sich die Volkswirtschaftsdirektorin nach der zweiten Ablehnung durch das BFM persönlich an dessen Direktor, um doch noch eine Zustimmung zu erreichen. Angesichts dieser Gesamtumstände kann die Beurteilung, die Weiterführung des Arbeitsverhältnisses sei nicht zumutbar gewesen, nicht als unhaltbar oder willkürlich bezeichnet werden. Daran ändert nichts, dass es stets um die Arbeitsbewilligung einer einzigen Person ging. Massgeblich ist vielmehr, dass die Beschwerdegegnerin in diesem Verfahren mehrfach - zu Unrecht - korrigiert und kritisiert wurde.
2.2.3 Weiter rügt der Kanton Zürich, der Beschwerdegegnerin hätten weniger weitgehende Massnahmen (z.B. ordentliche Kündigung, Aufsichtsbeschwerde, Anrufen des Ombudsmannes) zur Verfügung gestanden, welche sie zuerst hätte ergreifen müssen. Sinngemäss macht er damit eine Verletzung des Verhältnismässigkeitsprinzips nach Art. 5 Abs. 2 BV geltend, welche das Bundesgericht ausserhalb von Grundrechtseingriffen nur auf Willkür hin überprüft (<ref-ruling>).
Nach Ansicht der Vorinstanz standen der Beschwerdegegnerin keine zielführenden milderen Massnahmen als die fristlose Kündigung zur Verfügung. Das AWA habe mit dem Widerruf der von der Beschwerdegegnerin veranlassten Meldungen betreffend Schwarzarbeit, der Unterstützung des (zweiten) Wiedererwägungsgesuches, der Umteilung des strittigen Dossiers auf eine andere Mitarbeiterin u.a.m. der Beschwerdegegnerin deutlich zu verstehen gegeben, dass es an seinem Vorgehen festzuhalten gedenke. Alle diese Handlungen seien durch Vorgesetzte der Beschwerdegegnerin erfolgt. Das Einschalten der Ombudsstelle habe nicht verlangt werden können, da dadurch den Angestellten - anders als dem Staat - eine zusätzliche Hürde zur Ausübung der fristlosen Kündigung auferlegt werde. Auch könne nicht das vorgängige Einreichen einer Aufsichtsbeschwerde erwartet werden, wenn die Unzumutbarkeit der Fortsetzung des Arbeitsverhältnisses erstellt sei. Die Vorinstanz stützt sich somit auf sachliche Gründe. Es mag zwar zutreffen, dass auch eine andere Betrachtungsweise möglich gewesen wäre. Die Beurteilung erweist sich aber keinesfalls als unhaltbar und erfolgte daher willkürfrei.
2.2.4 Nach Ansicht des Kantons Zürich hat die Beschwerdegegnerin ihr Recht auf eine fristlose Kündigung verwirkt, da sie nach dem von Vorinstanz und Beschwerdegegnerin als massgeblich erachteten Zeitpunkt (14. Februar 2007) acht Tage zugewartet habe bis zur Einreichung der fristlosen Kündigung.
Es ist zunächst nicht zu beanstanden, dass die Vorinstanz die Rechtzeitigkeit der Kündigung anhand von Arbeitstagen und nicht von Kalendertagen bemessen hat, entspricht dies doch herrschender Lehre und Praxis zu Art. 337 OR (<ref-ruling> E. 4.4 S. 34; vgl. auch Ullin Streiff/Adrian von Kaenel, Arbeitsvertrag, 6. Aufl., 2006, N. 17 zu Art. 337 OR, Andreas Abegg, in: Gauch/Aepli/Stöckli [Hrsg.], Präjudizienbuch zum OR, 6. Aufl., 2006, N. 12 zu Art. 337 OR, Matthias Schwaibold, in: Heinrich Honsell [Hrsg.], Obligationenrecht, Art. 1-529, Kurzkommentar, 2008, N. 11 zu Art. 337, sowie Wolfgang Portmann/Jean-Fritz Stöckli, Schweizerisches Arbeitsrecht, 2. Aufl., 2007, Rz. 770). Die Begründung, weshalb die Beschwerdegegnerin bis zur fristlosen Kündigung noch fünf Arbeitstage zuwarten durfte, beruht im Weiteren auf sachlichen Kriterien (Chancen der Arbeitnehmerin auf dem Arbeitsmarkt, Tragweite des Entschlusses, Komplexität der Situation) und ist daher nicht willkürlich.
3. 3.1 Gemäss § 33 des Gesetzes des Kantons Zürich vom 27. September 1998 über das Arbeitsverhältnis des Staatspersonals (Personalgesetz, PG; LS 177.10) richtet sich der Weiterzug personalrechtlicher Entscheidungen durch das Staatspersonal nach dem Verwaltungsrechtspflegegesetz, soweit das Personalgesetz nichts Abweichendes regelt. Im Verwaltungsgerichtsbeschwerdeverfahren können nebst Rechtsverletzungen (einschliesslich Ermessensmissbrauch, -überschreitung und -unterschreitung; lit. a) auch eine unrichtige oder unvollständige Feststellung des Sachverhaltes (lit. b) sowie u.U. die Unangemessenheit der angefochtenen Verfügung gerügt werden (§ 20 Abs. 1 in Verbindung mit § 50 Abs. 1 des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959, VRG; LS 175.2).
Das Bundesgerichtsgesetz schreibt den Kantonen vor, dass die richterliche Vorinstanz des Bundesgerichts oder ein vorgängig zuständiges Gericht den Sachverhalt frei prüft und das Recht von Amtes wegen anwendet (Art. 110 BGG). Daraus folgt, dass der Sachverhalt im gerichtlichen Verfahren zu erstellen ist, weshalb diesem auch neue Tatsachen und Beweismittel unterbreitet werden können. Damit wird die Rechtsweggarantie von Art. 29a BV bzw. Art. 6 EMRK umgesetzt, welche eine uneingeschränkte Sachverhalts- und Rechtskontrolle durch (wenigstens) ein Gericht verlangt (Urteil 2C_651/2008 vom 20. April 2009 E. 4.2 mit Hinweisen).
3.2 Der Kanton Zürich macht schliesslich geltend, die Vorinstanz sei zu Unrecht von der Beurteilung des Regierungsrates im dieselben Vorfälle betreffenden Aufsichtsverfahren abgewichen und habe dadurch den Grundsatz der Gewaltenteilung verletzt.
Gemäss Art. 73 Abs. 2 der Verfassung des Kantons Zürich vom 27. Februar 2005 (KV; LS 101) sind die Gerichte in ihrer Rechtsprechung von den anderen Staatsgewalten unabhängig. Bei einer Bindung des Verwaltungsgerichts an die Feststellungen des Regierungsrates (Exekutive) wäre die Unabhängigkeit der Justiz und damit die Gewaltenteilung nach Art. 73 Abs. 2 KV nicht gewährleistet. Bereits aus diesem Grund ist nicht zu beanstanden, dass die Vorinstanz die Erstellung des Sachverhaltes und dessen rechtliche Würdigung frei und ungebunden vornahm.
Die Beschwerdegegnerin hat gestützt auf Art. 29a BV in Verbindung mit § 33 PG Anspruch auf richterliche Beurteilung der strittigen (Vermögens-)Fragen im Rahmen der Beendigung ihres Arbeitsverhältnisses (vgl. dazu Urteil 8C_453/2009 vom 7. April 2010, nach dessen E. 2 eine Verletzung von Art. 6 Ziff. 1 EMRK vorliegt, wenn im Rahmen eines öffentlich-rechtlichen Arbeitsverhältnisses keine gerichtliche kantonale Instanz gegeben ist; vgl. auch Andreas Kley, in: Die schweizerische Bundesverfassung, Ehrenzeller und andere [Hrsg.], 2. Aufl. 2008, N. 4, 11 und 14 zu Art. 29a BV). Damit hat sie auch Anspruch auf den verfassungsmässigen Richter im Sinne von Art. 30 BV (vgl. das erwähnte Urteil 8C_453/2009 sowie Gerold Steinmann, in: Die schweizerische Bundesverfassung, Ehrenzeller und andere [Hrsg.], 2. Aufl. 2008, N. 4 ff. zu Art. 30 BV). Dies beinhaltet den Anspruch auf mindestens eine unabhängige richterliche Instanz, welche nicht nur die Rechts-, sondern auch die Sachverhaltsfragen frei und ungebunden prüft (vgl. Kley, a.a.O., N. 11 zu Art. 29a BV sowie Bernhard Ehrenzeller, in: Basler Kommentar, Bundesgerichtsgesetz, 2008, N. 8 ff., insbesondere N. 17 zu Art. 110 BGG). Der Regierungsrat ist keine unabhängige richterliche Instanz in diesem Sinne, so dass die Vorinstanz nicht an dessen Feststellungen gebunden war, sondern zu Recht die Prüfung des Sachverhalts und auch die rechtliche Würdigung frei und ungebunden vornahm. Angesichts der beschränkten Kognition des Bundesgerichts (E. 1.1) war nur durch diesen Verfahrensablauf der Anspruch auf mindestens einmalige freie Überprüfung des Sachverhalts durch eine richterliche Instanz gewahrt. Der Vorwurf der Verletzung des Grundsatzes der Gewaltentrennung stösst damit ins Leere.
4. Das Verfahren ist kostenpflichtig. Der unterliegende Kanton war als Arbeitgeber und damit in seinem Vermögensinteresse tätig, weshalb er sich nicht auf die Befreiung von der Kostenpflicht gemäss Art. 66 Abs. 4 BGG berufen kann (<ref-ruling>) und die Gerichtskosten zu tragen hat (Art. 66 Abs. 1 BGG). Die Beschwerdegegnerin hat Anspruch auf eine Parteientschädigung (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich schriftlich mitgeteilt.
Luzern, 19. August 2010
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Riedi Hunold