Sachverhalt:
A. Mit Zahlungsbefehl vom 26. Oktober 2009 leitete die Z._ GmbH gegen X._ die Betreibung Nr. xxx des Betreibungsamtes Zürich 8 ein für Forderungen von Fr. 25'445.21 nebst Zins zu 5,12% seit 14. Oktober 2009, von Fr. 2'627.34 nebst Zins zu 5,12% seit 14. Oktober 2009, von Fr. 9'867.28 und von Fr. 411.52. Als Grund gab sie an: "Versäumnis-Urteil des Landgerichts Hamburg vom 27.06.2006. Kostenfestsetzungsbeschluss des Landgerichts Hamburg vom 17.10.2007. Umrechnungskurs: 1.00 EUR = 1.51690 CHF, Kursdatum: 13.10.2009".
B. Das für diese Beträge seitens der Gläubigerin gestellte Rechtsöffnungsgesuch wies das Bezirksgericht Zürich mit Verfügung vom 25. Januar 2012 ab. Demgegenüber erteilte das Obergericht des Kantons Zürich mit Urteil vom 22. März 2012 für die genannten Beträge unter inzidenter Anerkennung der ausländischen Urteile definitive Rechtsöffnung.
C. Gegen das obergerichtliche Urteil hat X._ am 4. Mai 2012 eine Beschwerde in Zivilsachen erhoben mit dem Begehren um dessen Aufhebung und Abweisung des Rechtsöffnungsgesuches, eventualiter um Rückweisung der Sache an das Obergericht. Mit Verfügung des präsidierenden Mitgliedes vom 29. Mai 2012 wurde der Antrag auf aufschiebende Wirkung abgewiesen. In der Sache selbst wurden keine Vernehmlassungen eingeholt, aber die kantonalen Akten beigezogen.

Erwägungen:
1. Der angefochtene Rechtsöffnungsentscheid ist ein kantonal letztinstanzlicher Endentscheid mit Fr. 30'000.-- übersteigendem Streitwert, gegen den grundsätzlich die Beschwerde in Zivilsachen ergriffen werden kann (Art. 72 Abs. 2 lit. a, Art. 74 Abs. 1 lit. b, Art. 75 Abs. 1 und Art. 90 BGG).
Der Rechtsöffnungsentscheid ist keine vorsorgliche Massnahme im Sinne von Art. 98 BGG, weshalb alle Rügen gemäss Art. 95 f. BGG zulässig sind und das Bundesgericht behauptete Rechtsverletzungen mit freier Kognition prüft (<ref-ruling> E. 1.5 S. 400). Inhaltlich ist indes die Auslegung ausländischen Rechts - nämlich von § 185 ZPO/D - Thema und es handelt sich um eine vermögensrechtliche Streitigkeit, weshalb einzig geprüft werden kann, ob das Obergericht dieses willkürlich angewandt hat (Art. 96 lit. b BGG i.V.m. Art. 9 BV als Bundesrecht i.S.v. Art. 95 lit. a BGG), was vom Beschwerdeführer auch so gerügt wird. Dabei gilt es zu beachten, dass für Verfassungsverletzungen das strenge Rügeprinzip gilt (Art. 106 Abs. 2 BGG). Das bedeutet, dass das Bundesgericht nur klar und detailliert erhobene und soweit möglich belegte Rügen prüft, während es auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid nicht eintritt. Wird die Verletzung des Willkürverbots gerügt, reicht es sodann nicht aus, die Lage aus Sicht des Beschwerdeführers darzulegen und den davon abweichenden angefochtenen Entscheid als willkürlich zu bezeichnen; vielmehr ist im Einzelnen darzulegen, inwiefern das kantonale Gericht willkürlich entschieden haben soll und der angefochtene Entscheid deshalb an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246).
2. Den betriebenen Forderungen liegt ein Versäumnisurteil bzw. ein Kostenfestsetzungsbeschluss des Landgerichtes Hamburg vom 27. Juni 2006 bzw. 17. Oktober 2007 zugrunde. Wie vom Obergericht zutreffend dargestellt (und auch nicht bestritten), hatte der Rechtsöffnungsrichter gestützt auf das vorliegend noch anwendbare alte Lugano-Übereinkommen vom 16. September 1988 (aLugÜ, SR 0.275.11) zu prüfen, ob dem Beschwerdeführer das verfahrenseinleitende Schriftstück ordnungsgemäss zugestellt worden war (Art. 27 Ziff. 2 aLugÜ), was sich nach den Regeln der deutschen Zivilprozessordnung (ZPO/D) bemisst. Das Landgericht Hamburg hatte die Klage dem Beschwerdeführer durch öffentliche Bekanntmachung zugestellt, was nach § 185 Ziff. 1 ZPO/D geschieht, wenn der Aufenthaltsort einer Person unbekannt und eine Zustellung an einen Vertreter oder Zustellungsbevollmächtigten nicht möglich ist. Zwischen den Parteien ist umstritten, ob genügend Abklärungen getroffen worden sind, um den Aufenthaltsort des Beschwerdeführers zu ermitteln, welcher im deutschen Verfahren der Beklagte war.
3. Das Bezirksgericht hat, worauf das Obergericht verweist, festgehalten, dass vom Beschwerdeführer sowohl in Berlin als auch in Miami falsche Anschriften existierten und ihm der Nachweis, wonach er sich ordnungsgemäss nach Miami abgemeldet habe, nicht gelungen sei. Das Bezirksgericht hat der Beschwerdegegnerin aber vorgeworfen, einem Hinweis im Beschluss des Amtsgerichts Charlottenburg vom 15. April 2005 nicht nachgegangen zu sein, gemäss welchem Rechtsanwalt Pfaff im Rahmen des Insolvenzverfahrens gegen die GmbH des Beschwerdeführers als Verfahrensbevollmächtigter aufgetreten sei; dieser hätte möglicherweise über den Aufenthalt des Beschwerdeführers Auskunft geben können. Die Beschwerdegegnerin hielt dem entgegen, dass Rechtsanwalt Y._ ihr nicht bekannt gewesen sei und sein Name lediglich im betreffenden Beschluss auftauche; im Übrigen sei er ausschliesslich Verfahrensbevollmächtigter der GmbH gewesen und nicht etwa ein allgemeiner Zustellungsbevollmächtigter des Beschwerdeführers.
Ausgehend von der einschlägigen Lehre zu § 185 ZPO/D (dazu E. 5) hat das Obergericht demgegenüber befunden, die Nachforschungen hätten sich vorliegend auf Anfragen beim Melderegister des Landeseinwohneramtes Berlin, beim Bezirksamt Charlottenburg-Wilmersdorf und beim Amtsgericht Charlottenburg sowie auf einen Auftrag an eine Privatdetektei und auf Recherchen im Internet erstreckt. Alle diese Massnahmen seien tauglich gewesen und § 185 Ziff. 1 ZPO/D verlange eine bestimmte Intensität der Nachforschungen, nicht aber bestimmte Handlungen. Der Beschwerdegegnerin könne deshalb nicht zum Vorwurf gereichen, dass sie nicht Rechtsanwalt Y._ um Auskunft angegangen sei; dies habe auch nicht nahe gelegen, nachdem sich die im fraglichen Beschluss des Amtsgerichtes Charlottenburg aufgeführte Adresse in Miami als inexistent erwiesen habe.
Das Obergericht hat weiter erwogen, dass der Beschwerdeführer dem Bezirksgericht zu Protokoll gegeben habe, von 1996 bis 2004 an der Brahmsstrasse 13 in Berlin gewohnt und sich beim Umzug in die USA am 1. August 2004 unter Hinterlegung der neuen Adresse ordnungsgemäss abgemeldet zu haben, was aber durch die aktenkundige Meldebescheinigung des Bezirksamtes Charlottenburg-Wilmersdorf widerlegt sei: Gemäss dieser Bescheinigung sei der Beschwerdeführer an einen unbekannten Ort in die Schweiz verzogen. Er habe also seine neue Adresse in den USA nicht hinterlegt, dies im Wissen, dass seine GmbH, deren einziger Geschäftsführer er gewesen sei, mit der Beschwerdegegnerin wegen einer Rechnung im Streit gelegen habe.
Das Obergericht ist zum Schluss gekommen, aufgrund all dieser Umstände sei die Zustellung der Klage durch öffentliche Bekanntmachung im Sinn von § 185 ZPO/D gerechtfertigt gewesen, womit Art. 27 Ziff. 2 aLugÜ einer Anerkennung des Versäumnisurteils des Landgerichtes Hamburg nicht entgegenstehe. Auch sonst seien keine Umstände ersichtlich, welche dessen Anerkennung und Vollstreckung entgegenstünden.
4. Nicht zu hören ist der Beschwerdeführer, soweit er in appellatorischer Weise eigene Tatsachenbehauptungen aufstellt (er habe sich in Deutschland ordnungsgemäss abgemeldet und sei aus beruflichen Gründen mit Frau und Kindern nach Florida gezogen, was seinem Umfeld bekannt gewesen sei, was man der Berliner Morgenpost habe entnehmen können und was sich auch aus einer einfachen Internet-Recherche ergeben hätte; der Beschwerdegegnerin habe unzweifelhaft auch aus einem Parallelverfahren gegen die W._ GmbH von seinen Aktivitäten in Florida wissen müssen; gemäss konstanter Praxis der deutschen Einwohnerbehörden werde bei Wegzug ins Ausland bzw. bei Ausländern im Meldeschein nicht die Nachfolgeadresse, sondern lediglich der Heimatstaat eingetragen; aufgrund dieser Tatsachen können von einem "Abtauchen" keine Rede sein), ohne zu zeigen, inwiefern das Obergericht bei der Sachverhaltsfeststellung in Willkür verfallen sein soll, zumal der Beschwerdeführer bei seinen Ausführungen nie von einer konkreten Adresse, sondern allgemein von "Florida" bzw. von "Miami" spricht.
5. In rechtlicher Hinsicht macht der Beschwerdeführer geltend, die öffentliche Zustellung sei eine ultima ratio, die nur in Frage komme, wenn alle Nachforschungen zum Aufenthalt fruchtlos geblieben seien. Die konkret vorgenommenen Abklärungen könnten nicht als "eingehende Ermittlungen" gelten. Insbesondere wären, weil es sich bei ihm um einen Ausländer handle, gemäss deutscher Lehre zu § 185 ZPO/D Nachforschungen beim Bundesverwaltungsamt in Köln zwingend nötig gewesen; indem das Obergericht solches nicht gefordert habe, sei es in Willkür verfallen. Im Übrigen hätte es nahe gelegen, sich bei Rechtsanwalt Y._ zu erkundigen oder allenfalls eine Zustellung vorzunehmen; auch hier seien keine ernsthaften Nachforschungen betrieben worden. Sodann habe das Obergericht mit dem Vorwurf, er sei gewissermassen untergetaucht, letztlich die Beweislast umgekehrt, was nicht angehe.
Aus den einschlägigen Kommentaren zu § 185 ZPO/D ergibt sich, dass von einem unbekannten Aufenthaltsort auszugehen ist, wenn dieser nicht nur dem Gericht, sondern auch der Allgemeinheit unbekannt und mit zumutbaren Nachforschungen nicht zu ermitteln ist, was grundsätzlich streng zu handhaben ist, aber auch nicht überspannt werden darf (HÄUBLEIN, in: Münchener Kommentar, 3. Aufl., N. 4 f. zu § 185 ZPO/D; ROTH, in: Stein/Jonas [Hrsg.], Kommentar zur Zivilprozessordnung, 22. Aufl., N. 6 zu § 185 ZPO/D; WOLST, in: Musielak [Hrsg.], Zivilprozessordnung Kommentar, 8. Aufl., N. 2 zu § 185 ZPO/D; BAUMBACH/LAUTERBACH/ALBERS/HARTMANN, Beck'scher Kurzkommentar zur Zivilprozessordnung, 67. Aufl., N. 5 zu § 185 ZPO/D). Während ein Teil der Lehre die zumutbaren Nachforschungen auf das Einwohnermeldeamt und die zuletzt zuständige Poststelle beschränken will (ROTH, a.a.O., N. 7), nennen andere Autoren als weitere Nachforschungsmöglichkeiten z.B. den ehemaligen Arbeitgeber, Vermieter, Hausgenossen, Verwandte sowie allenfalls das Sozialamt oder Bundesverwaltungsamt (HÄUBLEIN, a.a.O., N. 7; WOLST, a.a.O., N. 2) bzw. gegebenenfalls den Detektiv, Ehegatten, Geschäftsfreund, die Polizei, Sozialversicherung oder Ausländerbehörde (BAUMBACH/LAUTERBACH/ ALBERS/HARTMANN, a.a.O., N. 6 ff.).
Wie das Obergericht zutreffend festgehalten hat, sind aber so oder anders keine bestimmten Abklärungshandlungen gesetzlich vorgeschrieben, sondern müssen insgesamt mit genügender Intensität taugliche Nachforschungen betrieben worden sein. Die Nachfrage beim Bundesverwaltungsamt wird von verschiedenen Autoren erwähnt (HÄUBLEIN, a.a.O., N. 7; WOLST, a.a.O., N. 2; BAUMBACH/LAUTERBACH/ ALBERS/HARTMANN, a.a.O., N. 6), sie ist aber aufgrund der offenen Formulierung von § 185 ZPO/D nicht zwingend (HÄUBLEIN z.B. spricht davon, dass eine dortige Nachfrage geboten sein könne). In diesem Kontext ist mithin keine Willkür ersichtlich.
Was Rechtsanwalt Y._ anbelangt, setzt sich der Beschwerdeführer nicht mit der Begründung des Obergerichts auseinander, weshalb eine dortige Anfrage nicht nahe gelegen habe; mit der nicht weiter begründeten Behauptung des Gegenteils ist keine Willkür darzutun.
Schliesslich ist festzuhalten, dass das Obergericht unter Verweis auf das Bezirksgericht ausdrücklich festgehalten hat, es sei nicht (mehr) nachvollziehbar, wer die falschen Adressen in Berlin und Miami in Umlauf gebracht habe. Der implizite Vorwurf des Untertauchens beschränkt sich deshalb auf die für das Bundesgericht verbindlich festgehaltene (Art. 105 Abs. 1 BGG) und im Übrigen aktenkundige Tatsache, dass der Beschwerdeführer beim Einwohnermeldeamt nicht seine neue Adresse hinterlassen hat. Inwiefern damit eine Beweislastumkehr verbunden sein soll, ist im Übrigen unerfindlich.
Insgesamt ist nicht ersichtlich, inwiefern das Obergericht ausgehend von den aufgezählten Nachforschungsbemühungen und der Feststellung, dass der Aufenthaltsort nicht habe ausfindig gemacht werden können, sowie ausgehend von der weiteren impliziten Feststellung, dass es in Deutschland keinen Vertreter oder Zustellungsbevollmächtigten gegeben habe, in Willkür verfallen sein soll, wenn es davon ausgegangen ist, die Bedingungen für eine Zustellung der Klage durch öffentliche Bekanntmachung im Sinn von § 185 ZPO/D seien erfüllt gewesen.
6. Abschliessend rügt der Beschwerdeführer eine Gehörsverletzung, indem er im kantonalen Verfahren nicht anwaltlich vertreten gewesen sei und deshalb das Obergericht aus seiner Stellungnahme hätte herauslesen müssen, dass er geltend gemacht habe, in Miami ohne weiteres auffindbar gewesen zu sein.
Der Beschwerdeführer legt diesbezüglich den Ausdruck einer Google-Suche bei. Dabei handelt es sich um ein neues und damit unzulässiges Dokument (Art. 99 Abs. 1 BGG). Ohnehin ergibt sich daraus nur die Stadt "Miami", nicht aber eine dortige Adresse, was die obergerichtliche Aussage, eine Adresse sei auch mit tauglichen Nachforschungen nicht greifbar gewesen, gerade bekräftigt.
Im Übrigen ist nicht ersichtlich, inwiefern das Obergericht gegen das rechtliche Gehör des Beschwerdeführers verstossen haben könnte, hat es sich doch ausführlich mit seinen Vorbringen auseinandergesetzt und seinen Entscheid ausführlich begründet.
7. Zusammenfassend ergibt sich, dass die Beschwerde in Zivilsachen abzuweisen ist, soweit darauf eingetreten werden kann. Dem Beschwerdeführer sind mithin die Gerichtskosten aufzuerlegen (Art. 66 Abs. 1 BGG) und er hat die Beschwerdegegnerin für die Stellungnahme zum abgewiesenen Gesuch um aufschiebende Wirkung zu entschädigen (Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf eingetreten werden kann.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin mit Fr. 500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 21. Juni 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Möckli