Sachverhalt:
A. Das Bezirksgericht Horgen verurteilte X._ am 25. Februar 2009 wegen Betrugs und Veruntreuung zum Nachteil von Y._ zu einer bedingt vollziehbaren Freiheitsstrafe von 15 Monaten, als Zusatzstrafe zum Strafbefehl der Staatsanwaltschaft Limmattal/Albis vom 2. Juni 2008. Es verpflichtete X._, Fr. 37'110.-- zuzüglich Zins zu 5 % seit dem 27. Juli 1998 sowie eine Prozessentschädigung von Fr. 16'000.-- an Y._ zu bezahlen und verwies deren Schadenersatzbegehren im Mehrbetrag auf den Zivilweg.
B. Das Obergericht des Kantons Zürich sprach X._ am 16. November 2009 von den Vorwürfen der Veruntreuung und des Betrugs zum Nachteil von Y._ frei. Es hob die Verpflichtung von X._ zur Bezahlung der Zivilforderung und Prozessentschädigung an Y._ auf. Die Untersuchungs- und Verfahrenskosten beider Instanzen, inklusive der Kosten für die amtliche Verteidigung, auferlegte es X._ zur Hälfte und Y._ zu einem Viertel. Es verpflichtete Y._, X._ für die erbetene Verteidigung eine reduzierte Entschädigung von Fr. 7'500.-- sowie eine Umtriebsentschädigung von Fr. 750.-- zu bezahlen.
C. Gegen dieses Urteil erhebt Y._ Beschwerde in Strafsachen. Sie beantragt, das angefochtene Urteil sei vollumfänglich aufzuheben und zur Neubeurteilung an die Vorinstanz zurückzuweisen. Eventualiter seien Dispositivziffern 8 (Parteientschädigung von Fr. 7'500.-- an X._) und 10 (Umtriebsentschädigung von Fr. 750.-- an X._) aufzuheben und es sei von einer Entschädigung an X._ abzusehen.
D. X._ ficht den Kostenentscheid mit separater Beschwerde (6B_19/2010) an.
E. X._ beantragt in seiner Stellungnahme, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Soweit Dispositivziffern 8 und 10 des angefochtenen Entscheids aufgehoben würden, seien die entsprechenden Entschädigungszahlungen dem Kanton Zürich zu überbinden. Es sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
Das Obergericht sowie die Oberstaatsanwaltschaft des Kantons Zürich haben auf eine Vernehmlassung verzichtet.

Erwägungen:
1. 1.1 Die Beschwerdeführerin rügt, die Vorinstanz erachte ihre Zeugenaussage, die Aussage von P._ sowie die erste Einvernahme des angeschuldigten Beschwerdegegners 1 vom 22. Mai 2007 mangels Anwesenheit eines amtlichen Verteidigers unter Verletzung des Gebots von Treu und Glauben gemäss <ref-law> und <ref-law>, des Willkürverbots nach <ref-law> sowie des Rechts auf Beweis bzw. des Anspruchs auf rechtliches Gehör nach Art. 6 EMRK, <ref-law> und <ref-law> als unverwertbar. Der vorliegende Fall sei mit dem Urteil 6B_536/2009 vom 12. November 2009 vergleichbar, mit dem das Bundesgericht die Legitimation einer Geschädigten im Falle der Nichtverwertung der von ihr (privat) erstellten Videoaufnahmen bejaht habe. Auch sie sei vorliegend zur Beschwerde legitimiert, denn es handle sich um von ihr beantragte Beweismittel.
1.2 Gemäss <ref-law> ist zur Beschwerde in Strafsachen berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a) und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (lit. b). Die Beschwerdeführerin hat am vorinstanzlichen Verfahren teilgenommen. Sie fällt jedoch unter keine der in Art. 81 Abs. 1 lit. b Ziff. 1-6 BGG ausdrücklich aufgeführten Beschwerdeberechtigten. Namentlich ist sie nicht Opfer im Sinne von Art. 81 Abs. 1 lit. b Ziff. 5 BGG, da sie durch die angezeigten Straftaten nicht in ihrer körperlichen, psychischen oder sexuellen Integrität unmittelbar beeinträchtigt wurde. Als Geschädigte, die durch die von ihr angezeigten Straftaten (Betrug und Veruntreuung) lediglich einen finanziellen Schaden erlitten hat, ist sie zur vorliegenden Beschwerde grundsätzlich nicht legitimiert (<ref-ruling> E. 2 S. 229 ff. mit Hinweisen).
1.3 Unbekümmert um die fehlende Legitimation in der Sache selbst kann die Beschwerdeführerin die Verletzung von Rechten rügen, die ihr als am Verfahren beteiligte Partei nach dem massgebenden Prozessrecht oder unmittelbar aufgrund der BV oder der EMRK zustehen (BGE 6B_540/2009 vom 22. Oktober 2009 E. 1.9). Zulässig sind Rügen, die formeller Natur sind und die von der Prüfung der Sache selber getrennt werden können. Nicht zu hören sind Rügen, die im Ergebnis auf eine materielle Überprüfung des angefochtenen Entscheids abzielen (vgl. <ref-ruling> E. 1.3.2 S. 253; <ref-ruling> E. 6.2 S. 198 ff; je mit Hinweisen). Ein in der Sache nicht legitimierter Geschädigter kann deshalb weder die Beweiswürdigung kritisieren, noch kann er geltend machen, die Begründung sei materiell unzutreffend (<ref-ruling> E. 7b S. 94 mit Hinweisen).
1.4 Das Bundesgericht hat die Beschwerdelegitimation einer Geschädigten in einem Fall bejaht, in dem das kantonale Gericht die von ihr offerierten Beweise als unverwertbar bezeichnete und im kantonalen Verfahren unter Missachtung des Anspruchs auf rechtliches Gehör nach <ref-law> nicht berücksichtigte (vgl. Urteil 6B_536/2009 vom 12. November 2009 E. 1.4. mit Hinweis). Die Vorinstanz erachtet die Aussagen der Geschädigten, des Beschwerdegegners sowie eines Zeugen infolge fehlender Anwesenheit des amtlichen Verteidigers des Beschwerdegegners als nichtig. Sie hält wichtige Beweismittel aus formellen Gründen für unbeachtlich, was Auswirkungen auf die Beurteilung der Zivilforderung der Geschädigten und deren Anspruch auf Beweis hat. Auf die entsprechende Beschwerde ist demnach einzutreten.
1.5 Das Vorbringen der Beschwerdeführerin, die Vorinstanz spreche den Beschwerdegegner 1 zu Unrecht frei, stellt im Ergebnis eine Kritik an der vorinstanzlichen Begründung dar, die von der Prüfung der Sache nicht getrennt werden kann. Auf eine materiellrechtliche Überprüfung der Sache selber hat die Beschwerdeführerin als Geschädigte aber keinen Anspruch (vgl. E. 1.3), weshalb auf diese Rüge nicht einzutreten ist.
2. 2.1 Die Beschwerdeführerin macht geltend, der Beschwerdegegner 1 habe nach Bestellung des amtlichen Verteidigers auf ihre erneute Einvernahme explizit verzichtet. Sie habe sich auf den Verzicht verlassen dürfen. In der Befragung vom 21. November 2007 habe der Beschwerdegegner 1 zudem immer wieder auf seine früheren Aussagen verwiesen, weshalb auch diese verwertbar seien. Die erstmalige Berufung auf die Unverwertbarkeit der vor der Bestellung seines amtlichen Verteidigers erfolgten Einvernahmen (namentlich die Einvernahmen der Beschwerdeführerin und des Zeugen P._ je vom 5. Juli sowie zwei Einvernahmen des Beschwerdegegners 1 vom 22. Juli 2007) im Rechtsmittelverfahren sei rechtsmissbräuchlich nach <ref-law>, verstosse gegen das Willkürverbot nach <ref-law> sowie das Recht auf Beweis bzw. auf rechtliches Gehör nach <ref-law>.
2.2 Der in <ref-law> garantierte Anspruch auf rechtliches Gehör räumt dem Betroffenen das persönlichkeitsbezogene Mitwirkungsrecht ein, erhebliche Beweise beizubringen, mit solchen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise mitzuwirken. Dem Mitwirkungsrecht entspricht die Pflicht der Behörden, die Argumente und Verfahrensanträge der Partei entgegenzunehmen und zu prüfen, sowie die von ihr rechtzeitig und formrichtig angebotenen Beweismittel abzunehmen (vgl. <ref-ruling> E. 2b S. 56; <ref-ruling> E. 2b S. 102, je mit Hinweisen).
<ref-law> verpflichtet den Staat und Private, nach Treu und Glauben zu handeln. Diese Norm erfasst auch das widersprüchliche Verhalten (venire contra factum proprium). Setzt sich jemand zu seinem früheren Verhalten in Widerspruch, ist darin ein Verstoss gegen Treu und Glauben zu erblicken, wenn das frühere Verhalten ein schutzwürdiges Vertrauen begründet hat, welches durch die neuen Handlungen enttäuscht würde (vgl. Urteil 2C_446/2007 vom 22 Januar 2008 E. 3.1 mit Verweis auf <ref-ruling> E. 3 S. 130 f. in: StR 63/2008 S. 376 und StE 2008 B 96.11 Nr. 8). <ref-law> schützt das entsprechende Vertrauen im zivilrechtlichen Bereich (vgl. zum Gebot von Treu und Glauben nach <ref-law>: <ref-ruling> E. 5.1 S. 497; <ref-ruling> E. 2a S. 259; je mit Hinweisen).
Sowohl die Praxis des Bundesgerichtes als auch diejenige der Strassburger Rechtsprechungsorgane verlangen grundsätzlich, dass der Angeschuldigte oder sein Anwalt zur Wahrnehmung der Verteidigungsrechte rechtzeitig und in angemessener Weise aktiv werden müssen. Wenn eine entsprechend zumutbare Intervention unterbleibt, kann nach Treu und Glauben und von Grundrechts wegen kein Tätigwerden der Strafjustizbehörden erwartet werden (<ref-ruling> E. 2e/bb S. 55 mit Hinweisen).
Sowohl die Praxis des Bundesgerichtes als auch diejenige der Strassburger Rechtsprechungsorgane verlangen grundsätzlich, dass der Angeschuldigte oder sein Anwalt zur Wahrnehmung der Verteidigungsrechte rechtzeitig und in angemessener Weise aktiv werden müssen. Wenn eine entsprechend zumutbare Intervention unterbleibt, kann nach Treu und Glauben und von Grundrechts wegen kein Tätigwerden der Strafjustizbehörden erwartet werden (<ref-ruling> E. 2e/bb S. 55 mit Hinweisen).
2.3 2.3.1 Der bereits im kantonalen Verfahren anwaltlich vertretene Beschwerdegegner 1 unterliess es, die Unverwertbarkeit der Einvernahmen rechtzeitig geltend zu machen. Vielmehr machte er vor erster Instanz und auch noch im Rahmen seiner Berufungsschrift bloss materielle Ausführungen zu den Aussagen der Verfahrensbeteiligten. Spätestens als er in der Befragung vom 21. November 2007 im Beisein seines Verteidigers auf seine früheren Einvernahmen verwies und zu den Aussagen des Zeugen P._ vom 5. Juli 2007 befragt wurde, bzw. als ihn die Staatsanwaltschaft am 14. Januar 2008 anfragte, ob er eine weitere Einvernahme der Geschädigten wünsche, hatten er und sein Verteidiger Kenntnis vom behaupteten Mangel. Damit stand die Möglichkeit offen, dies schon vor der Anklageerhebung bzw. im erstinstanzlichen Verfahren zu rügen. Jedenfalls hätte eine solche Rüge erhoben werden müssen, nachdem das erstinstanzliche Gericht in der Urteilsbegründung auf die fraglichen Einvernahmen abstellte. Der Beschwerdegegner 1 brachte jedoch erstmals im Plädoyer anlässlich der Berufungsverhandlung vor, die Aussagen seien unverwertbar. Ein solches Zuwarten verstösst gegen den Grundsatz von Treu und Glauben nach <ref-law> (vgl. Urteil 6B_841/2009 vom 26. November 2009 E. 4.2).
2.3.2 Hinzu kommt, dass der Beschwerdegegner 1 im Ermittlungsverfahren gegenüber der Staatsanwaltschaft ausdrücklich und vorbehaltlos auf eine weitere Einvernahme der Beschwerdeführerin verzichtete (Beschwerdebeilagen 3 und 4). Entgegen seiner Auffassung lässt sich dem Verzicht nicht entnehmen, dass dieser unter dem Vorbehalt eines Freispruchs gestanden wäre. Grund für die Anfrage der Staatsanwaltschaft war einzig die fehlende Anwesenheit seines Verteidigers. Mit seiner Erklärung verzichtete er auf sein Recht, die belastenden Aussagen durch (entlastende) Gegenfragen in Zweifel zu ziehen (vgl. § 14 Abs. 1 StPO/ZH). Indem sich der Beschwerdegegner 1 nachträglich auf die Unverwertbarkeit der Aussage infolge fehlender Anwesenheit seines Verteidigers beruft, verstösst er gegen das Verbot widersprüchlichen Verhaltens (<ref-law>).
2.3.3 Die Beschwerde ist gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Bei diesem Ausgang des Verfahrens kann offen bleiben, ob die Auffassung der Vorinstanz zutrifft, wonach sie selbst den Mangel durch erneute Einvernahmen der Verfahrensbeteiligten nicht heilen könne. Immerhin ist festzuhalten, dass es sich nicht um eine zusätzliche Beweisabnahme oder Beweisergänzung, sondern vielmehr um eine Wiederholung bereits abgenommener Beweise handelt.
3. Der Beschwerdegegner 1 wird als unterliegende Partei kostenpflichtig (<ref-law>). Er stellt ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Dieses ist gutzuheissen, da seine Bedürftigkeit ausgewiesen ist (<ref-law>). Sein Standpunkt kann nicht als aussichtslos bezeichnet werden, da er sich der Auffassung der Vorinstanz anschliesst. Dem Kanton Zürich sind keine Kosten zu überbinden (<ref-law>).
Der Beschwerdeführerin ist eine Parteientschädigung zuzusprechen, welche der Beschwerdegegner 1 und der Kanton Zürich je hälftig zu tragen haben. Der Rechtsvertreter des Beschwerdegegners 1 ist zufolge unentgeltlicher Rechtspflege angemessen aus der Bundesgerichtskasse zu entschädigen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, das Urteil des Obergerichts des Kantons Zürich vom 16. November 2009 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch des Beschwerdegegners 1 um unentgeltliche Rechtspflege wird gutgeheissen. Für das bundesgerichtliche Verfahren wird ihm Rechtsanwalt Thomas Wirz als unentgeltlicher Anwalt beigegeben.
3. Es werden keine Gerichtskosten erhoben.
4.1 Der Kanton Zürich hat der Beschwerdeführerin für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 1'500.-- zu bezahlen.
4.1 Der Kanton Zürich hat der Beschwerdeführerin für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 1'500.-- zu bezahlen.
4.2 Der Beschwerdegegner 1 hat der Beschwerdeführerin für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 1'500.-- zu bezahlen.
5. Dem Vertreter des Beschwerdegegners 1, Rechtsanwalt Thomas Wirz, wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 3'000.-- ausgerichtet.
6. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 8. Juni 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch