Sachverhalt: A. X._ (1966) und Z._ (1970) haben die gemeinsamen Kinder S._ (2005) und T._ (2007). Mit Urteil des Gerichtshofes der persönlichen Fälle der Nicht-Muslime in Dubai (Vereinigte Arabische Emirate, VAE) vom 11. Januar 2010 wurde die Ehe zwischen den Parteien geschieden. S._ hält sich bei der Mutter in Zürich auf, T._ beim Vater in Dubai bzw. Abu Dhabi. B. Am 4. Januar 2013 stellte der Vater ein Gesuch um Rückführung der Tochter S._ nach Griechenland, innert fünf Tagen ab Rechtskraft des Entscheides und unter Androhung der Ungehorsamsstrafe. Ferner verlangte er, der Mutter für die Dauer des Verfahrens zu verbieten, das Kind ausser Landes zu bringen, und es seien die Parteien zu verpflichten, im Rahmen einer Mediation die freiwillige Rückkehr des Kindes oder eine gütliche Regelung zu bewirken. Mit Entscheid vom 14. Februar 2013 trat das Obergericht des Kantons Zürich auf das Gesuch nicht ein mit der Begründung, der gewöhnliche Aufenthalt von S._ in Griechenland vor der behaupteten Entführung in die Schweiz sei nicht (genügend) nachgewiesen und die VAE, wo die Parteien vorher gelebt hätten und der gesuchstellende Vater sein Domizil verzeige, seien nicht Vertragsstaat des Haager Rückführungsübereinkommens. C. Gegen diesen Entscheid hat der Vater am 28. Februar 2013 eine Beschwerde in Zivilsachen und eine subsidiäre Verfassungsbeschwerde eingereicht mit den Begehren, die Parteien seien zu verpflichten, im Rahmen einer Mediation eine freiwillige Rückführung des Kindes zu erreichen oder eine gütliche Regelung der Angelegenheit herbeizuführen, eventualiter sei auf das Rückführungsgesuch einzutreten und die Sache zur materiellen Beurteilung an das Obergericht zurückzuweisen, subeventualiter sei das Verfahren zur Neubeurteilung an die Vorinstanz zurückzuweisen. Mit Vernehmlassung vom 11. März 2013 hat die Beschwerdegegnerin auf Abweisung der Beschwerde geschlossen, soweit darauf einzutreten sei. Sie hat ferner ein Gesuch um unentgeltliche Rechtspflege gestellt. Am 17. April 2013 hat der Beschwerdeführer privat eine E-Mail mit Beilagen gesandt. D. Das Bundesgericht hat das Urteil am 18. April 2013 öffentlich beraten. 