Sachverhalt:
A. Z._ und X._ sind Mazedonier. Im Anschluss an ihre Heirat im Dezember 2001 lebten sie gemeinsam in der Schweiz. Am xxxx 2004 kam hier ihre Tochter Y._ zur Welt.
Am 18. August 2008 stellte Z._ beim Bezirksgericht Winterthur ein Eheschutzbegehren. Weil X._ am gleichen Tag in A._ (Mazedonien) das Scheidungsverfahren anhängig gemacht hatte, trat das Bezirksgericht Winterthur mit Entscheid vom 12. Dezember 2008 auf das Eheschutzgesuch nicht ein, erliess aber vorsorgliche Massnahmen, mit welchen Y._ unter die Obhut der Mutter gestellt und den Vater zu Unterhaltsbeiträgen von total Fr. 1'450.--, wovon Fr. 800.-- (zzgl. Kinderzulagen) für die Tochter, verpflichtet wurde.
Am 24. Dezember 2008 fand vor Amtsgericht Tetovo in Abwesenheit der Ehefrau die (erste) Hauptverhandlung statt, an welcher die Ehe geschieden wurde. Das Berufungsgericht Gostivar hob dieses Urteil am 14. April 2009 auf und wies die Sache an das Amtsgericht Tetovo zurück. Nach weiteren Verhandlungen am 14. Juli und 14. August 2009, an welchen die Ehefrau nunmehr teilnahm, schied das Amtsgericht am 24. September 2009 die Ehe, wiederum in Abwesenheit der Ehefrau. Dabei sprach es die elterliche Sorge dem Vater zu, unter Verpflichtung der Mutter zu Unterhaltsleistungen von 500 Denar pro Monat, und verpflichtete den Ehemann zu nachehelichen Unterhaltszahlungen an die Ehefrau von Fr. 150.-- pro Monat. Am 12. November 2009 bestätigte das Berufungsgericht Gostivar dieses Urteil. Dagegen soll nach Angaben der Ehefrau beim obersten Gericht der Republik Mazedonien ein Revisionsbegehren eingereicht worden sein.
B. Am 9. März 2010 ersuchte der Ehemann beim Bezirksgerichtspräsidium Münchwilen um Anerkennung und Vollstreckbarerklärung des mazedonischen Scheidungsurteils.
Mit Verfügung vom 28. Juli 2010 erklärte das Vizegerichtspräsidium Münchwilen das Scheidungsurteil des Amtsgerichts Tetovo, bestätigt durch das Berufungsgericht Gostivar, in der Schweiz als anerkannt und für vollstreckbar.
Demgegenüber anerkannte das Obergericht des Kantons Thurgau an seiner Sitzung vom 25. Oktober 2010 in teilweiser Gutheissung des Rekurses der Ehefrau nur den Scheidungspunkt, während es den Nebenfolgen wegen Verletzung des Ordre public die Anerkennung versagte.
C. Dagegen hat der Ehemann am 6. Januar 2011 eine Beschwerde in Zivilsachen eingereicht mit den Begehren um Aufhebung, soweit dem Scheidungsurteil die Anerkennung versagt werde, bzw. um Bestätigung der Verfügung des Vizepräsidiums Münchwilen und um Anerkennung und Vollstreckbarerklärung des Scheidungsurteils auch mit Bezug auf die Nebenfolgen, eventualiter um Rückweisung der Sache an das Obergericht. Mit Beschwerdeantwort vom 14. April 2011 verlangt die Ehefrau die Abweisung der Beschwerde. Ausserdem ersuchen beide Parteien um unentgeltliche Rechtspflege.

Erwägungen:
1. Angefochten ist der kantonal letztinstanzliche Entscheid über die Anerkennung eines ausländischen Scheidungsurteils, wogegen die Beschwerde in Zivilsachen gegeben ist (Art. 72 Abs. 2 lit. b Ziff. 1, Art. 75 Abs. 1 und Art. 90 BGG), und zwar unabhängig von einem Streitwert, weil namentlich auch die Nebenfolge der Sorgerechtszuteilung vor Bundesgericht angefochten bleibt (Urteil 5A_131/2011 vom 31. März 2011 E. 1.1). Die Beschwerde in Zivilsachen steht damit grundsätzlich offen; inwiefern auf die einzelnen Vorbringen einzutreten ist, wird im jeweiligen Sachzusammenhang zu erörtern sein.
2. Vor Bundesgericht ist einzig noch die Anerkennung der Scheidungsnebenfolgen umstritten. Diesbezüglich hat das Obergericht erwogen, ein Unterhaltsbeitrag von Fr. 150.-- entspreche offensichtlich nicht dem Bedarf der Ehefrau und der Leistungsfähigkeit des Ehemannes; insgesamt würde die Unterhaltsregelung aber wohl dann nicht gegen den Ordre public verstossen, wenn auch die Sorgerechtsregelung anerkannt würde und der Vater demnach umfassend für die Tochter aufzukommen hätte. Was dies anbetreffe, so sei Mazedonien nicht Vertragsstaat des Haager Übereinkommens über die Zuständigkeit der Behörden und das anzuwendende Recht auf dem Gebiet des Schutzes von Minderjährigen (MSA, SR 0.211.231.01) und des Haager Übereinkommens über die Zuständigkeit, das anzuwendende Recht, die Anerkennung, Vollstreckung und Zusammenarbeit auf dem Gebiet der elterlichen Verantwortung und der Massnahmen zum Schutz von Kindern (HKsÜ, SR 0.211.231.011). Hingegen habe Mazedonien das Europäische Übereinkommen über die Anerkennung und Vollstreckung von Entscheidungen über das Sorgerecht für Kinder und die Wiederherstellung des Sorgerechts (ESÜ, SR 0.211.230.01) unterzeichnet. Gemäss Art. 7 ESÜ seien Sorgerechtsentscheidungen in den anderen Vertragsstaaten anzuerkennen, wenn sie im Ursprungsstaat vollstreckbar seien. Nach Art. 10 lit. a ESÜ sei die Anerkennung aber zu verweigern, wenn die Sorgerechtszuteilung mit den Grundwerten des Familien- und Kindschaftsrechts offensichtlich unvereinbar sei. Dies treffe vorliegend zu: Im Rahmen der vorsorglichen Massnahmen sei die Tochter unter die Obhut der Mutter gestellt worden, bei welcher sie seither lebe. Der Vater sei damals mit dieser Obhutsregelung einverstanden gewesen und es sei deshalb nicht nachvollziehbar, dass das Scheidungsgericht in Tetovo die elterliche Sorge dem Vater zugeteilt habe, nur weil die Mutter an Multipler Sklerose leide. Der Vater sei zu 100% erwerbstätig, während die Mutter keiner Erwerbstätigkeit nachgehe. Es sei nicht bekannt, wer die Tochter betreuen soll, wenn sie beim Vater wäre; hingegen sei die Mutter offensichtlich in der Lage, die Tochter zu betreuen, zumal ihr ein Erziehungsbeistand zur Seite stehe. Bei einem Vollzug des mazedonischen Urteils müsste die Tochter aus der jetzigen Situation herausgerissen werden. Die Sorgerechtsumteilung sei krass stossend und könne daher nicht anerkannt werden. Lebe die Tochter aber weiterhin bei der Mutter, sei der nacheheliche Unterhalt von Fr. 150.-- viel zu niedrig und verstosse das mazedonische Urteil auch in dieser Hinsicht gegen den materiellen Ordre public. Weil das Scheidungsurteil das Güterrecht und die Teilung der beruflichen Vorsorge nicht regle, müsse es in der Schweiz ohnehin ergänzt werden; entsprechend dem Grundsatz der Einheit des Scheidungsurteils sei es deshalb sinnvoll, sämtliche Scheidungsnebenfolgen in einem Zug zu regeln.
3. Der Beschwerdeführer macht geltend, die mazedonischen Gerichte hätten nichts gemacht, was in der Schweiz nicht auch möglich wäre. Insbesondere hätten sie sich bei der Zuteilung der elterlichen Sorge vom Kindeswohl leiten lassen und Y._ infolge der Erkrankung der Mutter ihm zugeteilt. Er arbeite in der Regel Frühschicht und komme um 14 Uhr nach Hause, so dass er die Tochter problemlos betreuen könne, jedenfalls besser als die Mutter, welche aufgrund ihres Gesundheitszustandes bereits jetzt auf Fremdbetreuung angewiesen sei. Im Übrigen wohnten Mutter und Tochter erst seit Dezember 2008 in B._; den grösseren Teil ihres Lebens habe Y._ in der elterlichen Wohnung in C._ verbracht, wo sie auch in den Kindergarten gegangen sei. Die obergerichtliche Behauptung, mit einer Umteilung an den Vater werde sie aus ihrem Umfeld herausgerissen, treffe deshalb nicht zu; Y._ habe ihre Freunde in C._ und es sei deshalb sinnvoller, wenn sie dort zur Schule gehe. Inwiefern die Sorgerechtszuteilung gegen den Ordre public verstossen soll, sei vor diesem Hintergrund nicht ersichtlich. Soweit die Tochter bei ihm lebe, könne aber auch die Regelung des nachehelichen Unterhalts nicht gegen den Ordre public verstossen.
Die Beschwerdegegnerin bestreitet vernehmlassungsweise, dass das mazedonische Scheidungsgericht für die Regelung der Scheidungsnebenfolgen zuständig war. Im Übrigen habe es nie persönliche Gespräche mit ihr oder der Tochter gegeben und das mazedonische Scheidungsgericht habe auch keine Beweise eingehend geprüft, wie dies der Beschwerdeführer zu Unrecht behaupte; unzutreffend sei sodann die Behauptung, das Berufungsgericht Gostivar habe sich eingehend mit den Vorbringen der Parteien auseinandergesetzt. Der Beschwerdeführer habe sich wieder verheiratet und die neue Ehefrau liebe Y._ nicht; es erstaune deshalb wenig, dass die Tochter nicht beim Vater wohnen wolle. Er könne sich angesichts seiner vollzeitigen Erwerbstätigkeit auch gar nicht um die Tochter kümmern, während sie (Mutter) dies bislang trotz ihrer Behinderung problemlos habe bewältigen können; sie müsse zweimal pro Woche für eine halbe Stunde zur Physiotherapie und erhalte einmal wöchentlich eine Spritze, so dass sie nie lange abwesend sei. Die Sorgerechtszuteilung entspreche in keiner Weise dem Kindeswohl bzw. den Grundwerten des Familien- und Kindschaftsrechts (Art. 10 Ziff. 1 lit. a ESÜ) und insbesondere auch nicht den aktuellen Verhältnissen (Art. 10 Ziff. 1 lit. b ESÜ). Sodann habe die Tochter ihren gewöhnlichen Aufenthalt ununterbrochen in der Schweiz und keine solche Beziehung zu Mazedonien gehabt (Art. 10 Ziff. 1 lit. c ESÜ); sie selbst (Mutter) lebe seit über zehn Jahren in der Schweiz und auch ihre Eltern und ihre beiden Brüder samt Familien würden in der Schweiz wohnen, die Tochter sei hier geboren worden und seither hier aufgewachsen, weshalb sie gar nie eine enge Beziehung zu Mazedonien habe aufbauen können. Was die Unterhaltsregelung anbelange, habe es dem mazedonischen Gericht angesichts des gewöhnlichen Aufenthaltes des Kindes in der Schweiz wiederum an Zuständigkeit gemangelt. Mit Bezug auf den nachehelichen Unterhalt liege zwar Einlassung vor, weshalb die indirekte Zuständigkeit nicht bestritten werde; in der Höhe verstosse der Unterhaltsbeitrag aber gegen den Ordre public, weil ihre Bedürfnisse mit Fr. 150.-- nicht ansatzweise gedeckt würden und deshalb in unerträglicher Weise gegen das schweizerische Rechtsempfinden verstossen würde.
4. In den Rechtsschriften wird weder behauptet noch ausgeführt, dass und inwiefern die kantonalen Sachverhaltsfeststellungen gegen verfassungsmässige Rechte verstossen würden (Art. 97 Abs. 1 und Art. 106 Abs. 2 BGG). Weil die betreffenden Feststellungen dem bundesgerichtlichen Urteil zugrunde zu legen sind (<ref-law>), soweit nicht eine Ergänzung von Amtes wegen erfolgt (<ref-law>), kann auf die Vorbringen und appellatorischen Sachverhaltsschilderungen der Parteien nicht eingetreten werden, soweit sie sich nicht aus dem obergerichtlichen Urteil ergeben (vgl. <ref-law>).
Den Ausführungen in der Beschwerde kann insoweit gefolgt werden, als nicht ersichtlich ist, inwieweit das Amtsgericht Tetovo mit der Zuteilung der Tochter an den Vater gegen den materiellen Ordre public verstossen haben soll: Eine Zuteilung an einen erwerbstätigen Elternteil ist dem schweizerischen Recht nicht fremd und das Scheidungsgericht hat auf die Erkrankung der Mutter hingewiesen. Auch wenn das diesbezügliche Beweisverfahren oberflächlich geblieben sein mag (deutsche Urteilsübersetzung: "Das Gericht beim schätzen alle diese Beweise einzeln und im Sinne eines logischen Gesamtumfanges"), so geht aus dem Urteil doch in groben Zügen hervor, was die Überlegungen des Scheidungsgerichts waren (deutsche Übersetzung: "Im Verlauf der Ehe die Angeklagte, erkrankte sich, was wegen Sie weder die alltäglichen Haushaltstätigkeiten erledigen, auch nicht für Ihren Kind sorgen könnte, wofür Ihre Verwandte aus dem gleichen Stadt, um für Ihre Haushalt zu sorgen, zu ihr gekommen sind, zwar persönlich für Sie und für Ihren Minderjährigen Kind (Sie haben gesäubert, gekocht, bügelten, auf das Kind aufgepasst, haben das Kind ernährt und ähnliches erledigt). Dar die Krankheit des Angeklagten immer mehr fortgeschritten ist, die Ehe Verhältnisse zwischen den Ehepartnern sind verschlechtert, insbesondere wegen den Wunsch des Klägers noch nachwuchs zu haben, was die Angeklagte nicht in die Lage ist zu machen. Bei so einem festgestellten Tatbestand das Gericht hat eine Entscheidung wie am Urteilsdispositiv getroffen, auch wegen folgendes: Im Konkretfall, die Angeklagte leidet an Multiple Sklerose, wofür für Sie persönlich 24 Stunden pflege vom Drittperson erforderlich ist, das wegen sie kann nicht für Ihren 4 Jahre alten Kind sorgen"). Ausgehend von diesen Sachverhaltsfeststellungen - deren Richtigkeit im Anerkennungsverfahren nicht überprüft werden kann (vgl. <ref-law>) -, wonach die Beschwerdegegnerin rund um die Uhr auf Fremdhilfe angewiesen sei und deswegen nicht für ihr Kind sorgen könne, wäre unter Umständen auch ein schweizerisches Gericht zum Schluss gelangt, dass sich eine Zuteilung an den Vater aufdränge; jedenfalls ist nicht ersichtlich, inwiefern die entsprechende mazedonische Entscheidung vor dem Hintergrund der getroffenen Sachverhaltsfeststellungen gegen den schweizerischen Ordre public verstossen soll.
Wie die Beschwerdegegnerin zutreffend festhält, fehlt es indes an der indirekten Zuständigkeit der mazedonischen Gerichte: Die am xxxx 2004 geborene Tochter hat ihr ganzes Leben ununterbrochen in der Schweiz verbracht (seit dem 1. März 2003 befand sich die eheliche Wohnung in C._, vgl. Verfügung des Bezirksgerichts Winterthur vom 12. Dezember 2008, S. 6), wo sie auch in den Kindergarten geht und demnächst eingeschult wird. Mithin befand und befindet sich ihr gewöhnlicher Aufenthalt in der Schweiz, wo auch beide Elternteilen seit ihrer Geburt ununterbrochen leben. Der Vater geht hier einer vollzeitigen Erwerbstätigkeit nach und die Mutter verfügt zufolge ihrer Erkrankung über eine IV-Rente. Mit Ausnahme der formalen Staatsangehörigkeit sind keine Bezugspunkte des Kindes zu Mazedonien aktenkundig.
Gemäss Art. 7 ESÜ werden Sorgerechtsentscheidungen, die in einem Vertragsstaat ergangen sind, in jedem anderen Vertragsstaat anerkannt und, wenn sie im Ursprungsstaat vollstreckbar sind, für vollstreckbar erklärt. Gemäss dem in der Vernehmlassung thematisierten Art. 10 Ziff. 1 lit. c i) ESÜ ist die Anerkennung und Vollstreckung der Sorgerechtsentscheidung jedoch zu versagen, wenn das Kind Angehöriger des ersuchten Staates war oder dort seinen gewöhnlichen Aufenthalt hatte und keine solche Beziehung zum Ursprungsstaat bestand. Der explanatory Report zum ESÜ führt hierzu aus: "The purpose of paragraph 1, sub-paragraph c. i and ii, of this Article is to enable recognition and enforcement to be refused where the child's links with the State addressed are substantial and where he had no such links with the State of origin or if the only link is that he is a dual national." Eine indirekte Zuständigkeit besteht also dann nicht, wenn die Bezüge des Kindes zum Anerkennungsstaat sehr eng bzw. viel stärker sind als diejenigen zum Ursprungsstaat (vgl. GMÜNDER, Anerkennung und Vollstreckung von ausländischen Scheidungsurteilen unter besonderer Berücksichtigung von kindesrechtlichen Nebenfolgen, Diss. St. Gallen 2006, S. 138; SIEHR, in Münchener Kommentar, Band 10, 5. Aufl. 2010, Anhang III zu Art. 21 EGBGB N 42; BUCHER, L'enfant en droit international privé, Genf 2003, Rz. 423). Das ESÜ enthält damit den gleichen Gedanken, wie er sich auch aus Art. 1 MSA bzw. <ref-law> ergibt (auf welche Abkommen <ref-law> bis Juni 2009 verwies bzw. ab Juli 2009 verweist), wonach grundsätzlich das Gericht am gewöhnlichen Aufenthaltsort des Kindes für die Regelung u.a. der Sorgerechte zuständig ist. Dieses ist in der Regel viel besser in der Lage, die notwendigen Beweise zu erheben und sich von der Situation bzw. dem Umfeld des Kindes ein persönliches Bild zu machen.
Die Regelung des Kindesunterhalts und des (im mazedonischen Urteil nicht behandelten) Besuchsrechts ist untrennbar mit der Kindeszuteilung verbunden, weshalb über diese Fragen unabhängig von den hierfür anwendbaren Anerkennungsnormen ebenfalls neu zu befinden ist, soweit die Zuteilung nicht anerkannt werden kann (<ref-ruling> E. 2a/bb S. 303), was nach dem Gesagten vorliegend der Fall ist. Davon zu unterscheiden ist die Anerkennung und Vollstreckbarerklärung des Ehegattenunterhalts, der sich vorliegend nach den einschlägigen Normen des IPRG richtet, weil Mazedonien weder das Haager Übereinkommen über die Anerkennung und Vollstreckung von Unterhaltsentscheidungen (SR 0.211.213.02) noch das Lugano-Übereinkommen (LugÜ, SR 0.275.11 bzw. 0.275.12) unterzeichnet hat.
Das Obergericht hat befunden, für den Fall der Nichtanerkennung der Kindeszuteilung sei das Scheidungsurteil mit Bezug auf den weder den Bedürfnissen der Ehefrau noch der Leistungsfähigkeit des Ehemannes gerecht werdenden nachehelichen Unterhalt im Sinn von <ref-law> mit dem schweizerischen Ordre public offensichtlich unvereinbar, weshalb auch über diese Scheidungsnebenfolge in der Schweiz neu zu urteilen sei. Der Beschwerdeführer anerkennt diese Erwägungen letztlich, indem er in der Beschwerde auf S. 21 festhält: "Wie die Situation bei einer Sorgerechtszuteilung an die Mutter zu beurteilen wäre, muss offen gelassen werden, weil das Scheidungsgericht in Mazedonien diese Frage nicht abgeklärt hat und die entsprechenden Berechnungsgrundlagen fehlen." Jedenfalls sind diese Ausführungen nicht geeignet, eine falsche Rechtsanwendung durch das Obergericht zu begründen, und das Bundesgericht prüft angesichts der Begründungspflicht gemäss <ref-law> nur behauptete und wenigstens kurz begründete Rechtsverletzungen (<ref-ruling> E. 2.1 S. 245 f.). Das angefochtene Urteil ist deshalb auch in diesem Punkt zu schützen.
5. Zusammenfassend ergibt sich, dass die Beschwerde in Zivilsachen abzuweisen ist, soweit darauf eingetreten werden kann. Damit wird der Beschwerdeführer grundsätzlich kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG). Beide Parteien verlangen die unentgeltliche Rechtspflege. Wie die vorstehenden Erwägungen zeigen, muss die Beschwerde als von Anfang an aussichtslos bezeichnet werden, weshalb es auf Seiten des Beschwerdeführers an den materiellen Voraussetzungen für die unentgeltliche Rechtspflege fehlt (<ref-law>) und das entsprechende Gesuch abgewiesen werden muss. Auf Seiten der Beschwerdegegnerin sind sowohl die formellen als auch die materiellen Voraussetzungen erfüllt. Ihr Gesuch ist indessen gegenstandslos geworden, soweit es die Befreiung von den Gerichtskosten betrifft. Dagegen ist es bezüglich der Verbeiständung nur unter Vorbehalt der Einbringlichkeit der Parteientschädigung gegenstandslos. Soweit diese uneinbringlich ist, wäre ihre Rechtsvertreterin aus der Bundesgerichtskasse zu entschädigen (<ref-law>; <ref-ruling> E. 3d S. 326 f.).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird abgewiesen.
3. Das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege wird gutgeheissen, soweit es nicht gegenstandslos ist, und es wird ihr Rechtsanwältin Dominique Leemann als amtliche Vertreterin bestellt.
4. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
5. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen. Bei Uneinbringlichkeit wird Rechtsanwältin Dominique Leemann aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
6. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Thurgau schriftlich mitgeteilt.
Lausanne, 20. Juni 2011
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Möckli