Sachverhalt:
A. A.a Mit Urteil vom 8. Mai 2008 verpflichtete das Arbeitsgericht Koblenz die Z._ AG, Deutschland, zur Bezahlung einer Bruttoarbeitsvergütung von insgesamt EUR 29'966.73 nebst Zins an X._ (je EUR 2'700.-- für die Monate Juni 2007 bis April 2008 nebst Zins zu 5% über dem Basissatz, jeweils seit dem 20. eines jeden Monats, abzüglich je EUR 1'765.09 Insolvenzgeld für die Monate Oktober, November und Dezember 2007 [Ziff. 2], zuzüglich den Nettobetrag von EUR 5'562.-- nebst Zins zu 5% über dem Basissatz seit 1. Juni 2007 [Ziff. 4]).
A.b Mit Begehren vom 22. Mai 2009 betrieb X._ die Z._ AG mit Sitz an der A._strasse in B._ für eine Forderung von Fr. 45'564.50 (EUR 29'966.79 zum Kurs vom 22. Mai 2009 von 1.5205) nebst laufendem Zins und aufgelaufenem Zins von Fr. 6'722.79 (EUR 4'421.44 zum Kurs vom 22. Mai 2009 von 1.5205; Betreibung-Nr. ... des Betreibungsamtes B._).
Nachdem die Z._ AG Rechtsvorschlag erhoben hatte, erteilte der Einzelrichter im summarischen Verfahren des Bezirks Zürich X._ mit Verfügung vom 18. August 2009 definitive Rechtsöffnung für Fr. 45'564.50 (EUR 29'966.79 zum Kurs von 1.5205) nebst Zins zu 5% über dem jeweiligen deutschen Basiszinssatz seit 1. Januar 2010, nebst Zins zu 5.12% vom 1. Juli 2009 bis 31. Dezember 2009, nebst Zins zu 6.62% vom 1. Juni 2009 bis 30. Juni 2009 sowie für Fr. 6'722.79 (EUR 4'421.44 zum Kurs von 1.5205).
B. Mit Beschluss vom 21. Januar 2010 wies das Obergericht des Kantons Zürich auf Rekurs der Z._ AG das Rechtsöffnungsbegehren ab. Das Obergericht hielt im Wesentlichen dafür, die ordnungsgemässe Zustellung des als Rechtsöffnungstitel dienenden deutschen Urteils könne nicht nachgewiesen werden, da auf dem Zustellungszeugnis wesentliche Angaben fehlten.
C. Gegen diesen ihm am 27. Januar 2010 zugestellten Entscheid hat X._ (Beschwerdeführer) mit einer am 24. Februar 2010 der Post aufgegebenen Eingabe beim Bundesgericht Beschwerde in Zivilsachen eingereicht. Er beantragt, ihm sei in der Betreibung Nr. ... des Betreibungsamtes B._ für den Betrag von Fr. 45'564.50 nebst Zins zu 6.62% seit dem 1. Juni 2009, für Fr. 6'722.79 an aufgerechnetem Zins bis 31. Mai 2009 sowie für die Kosten des Zahlungsbefehls von Fr. 100.-- definitive Rechtsöffnung zu gewähren. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Der Beschwerdeführer hat seine Beschwerde mit einer weiteren Eingabe vom 25. Februar 2010 (eingegangen beim Bundesgericht am 26. Februar 2010) ergänzt. Eine weitere Eingabe erfolgte am 12. Mai 2010.
Das Obergericht hat sich am 28. Juni 2010 vernehmen lassen, hat sich aber nicht zu den Erwägungen des angefochtenen Beschlusses geäussert. Die Z._ AG (Beschwerdegegnerin) beantragt in ihrer Eingabe vom 6. Juli 2010, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Angefochten ist ein Rekursentscheid des Obergerichts des Kantons Zürich betreffend definitive Rechtsöffnung, mit dem vorfrageweise über die Anerkennung eines ausländischen Urteils befunden worden ist. Damit liegt ein Endentscheid (<ref-law>) über eine Schuldbetreibungs- und Konkurssache vor (Urteil 5A_840/2009 vom 30. April 2010 E. 1), deren Streitwert den Betrag von <ref-law> bei Weitem übersteigt. Die Beschwerde in Zivilsachen ist damit grundsätzlich gegeben. Rechtsöffnungsentscheide gelten nicht als vorsorgliche Massnahmen nach <ref-law> (<ref-ruling>), weshalb mit der Beschwerde auch eine Verletzung von Völkerrecht (<ref-law>), insbesondere des Haager Übereinkommens über die Zustellung gerichtlicher und aussergerichtlicher Schriftstücke im Ausland in Zivil- und Handelssachen (HZÜ65; SR 0.274.131) oder des Übereinkommens über die gerichtliche Zuständigkeit und die Vollstreckung gerichtlicher Entscheidungen in Zivil- und Handelssachen (LugÜ; SR 0.275.11) gerügt werden kann. Das Bundesgericht prüft dabei frei, ob Bestimmungen dieser Übereinkommen verletzt worden sind.
1.2 Als Nächstes fragt sich, ob ein letztinstanzlicher Endentscheid vorliegt (<ref-law>). Gegen Rekursentscheide kann nach <ref-law>/ZH Nichtigkeitsbeschwerde erhoben werden, wenn geltend gemacht wird, der angefochtene Entscheid beruhe zum Nachteil des Nichtigkeitsklägers auf der Verletzung eines wesentlichen Verfahrensgrundsatzes (Ziff. 1), auf einer aktenwidrigen oder willkürlichen tatsächlichen Annahme (Ziff. 2) oder auf einer Verletzung klaren materiellen Rechts (Ziff. 3). Ausgeschlossen ist die Nichtigkeitsbeschwerde, wenn das Bundesgericht einen Mangel frei überprüfen kann (<ref-law>/ZH; <ref-ruling> E. 3.2 S. 587). Im vorliegenden Fall geht es ausschliesslich um die Rechtsfrage, ob einem ausländischen Urteil wegen Fehlens gewisser Angaben auf dem in der Schweiz ausgestellten Zustellungszeugnis die Anerkennung zu versagen ist. Da das Bundesgericht insoweit die Anwendung des Völkerrechts frei überprüfen kann (E. 1.1 hiervor), erweist sich die kantonale Nichtigkeitsbeschwerde als unzulässig und der angefochtene Beschluss somit als letztinstanzlich im Sinn von <ref-law>.
1.3 Der angefochtene Entscheid ist dem Beschwerdeführer laut eigenen Angaben am 27. Januar 2010 zugestellt worden, womit die Beschwerdefrist (<ref-law>) am Freitag, 26. Februar 2010 abgelaufen ist. Die Beschwerde vom 24. Februar 2010 sowie die Eingabe vom 25. Februar 2010 sind damit rechtzeitig erfolgt. Verspätet ist dagegen die Ergänzung vom 12. Mai 2010. Darauf und auf die entsprechenden Ausführungen in der Beschwerdeantwort ist nicht einzutreten.
1.4 Der Beschwerdeführer verweist in seiner Beschwerde auf weitere für den Nachweis der ordnungsgemässen Zustellung beim Obergericht mit der Rekursantwort aufgeführte Tatsachen und zu deren Beweis beigebrachte Belege. Das Obergericht hat in seinem Urteil in keiner Weise darauf Bezug genommen und hat keine entsprechenden tatsächlichen Feststellungen getroffen. Die Vorbringen mitsamt den damit verbundenen Ausführungen des Beschwerdeführers zu den tatsächlichen Verhältnissen gelten damit als neu (<ref-law>). Diese neuen Tatsachen und Beweismittel wären ausnahmsweise zulässig, wenn sie geeignet wären, die nachträgliche rechtmässige Zustellung nachzuweisen. Denn dadurch würde das rechtlich geschützte Interesse des Beschwerdeführers an einer Beurteilung der vorliegenden Beschwerde hinfällig und es müsste darauf nicht eingetreten werden (<ref-ruling> E. 2.1). Die neuen Vorbringen sind jedoch nicht schlüssig, weshalb die Beschwerde materiell zu behandeln ist.
2. 2.1 Vorliegend geht es um die Vollstreckung einer vom Amtsgericht Koblenz mit Urteil vom 8. Mai 2008 dem Beschwerdeführer zugesprochenen Entschädigung aus einem Arbeitsverhältnis. Dabei handelt es sich um eine Zivil- und Handelssache im Sinn von <ref-law>. Dieses Abkommen ist für die Schweiz am 1. Januar 1992 und für Deutschland am 1. März 1995 in Kraft getreten und geht somit dem Bundesgesetz über das Internationale Privatrecht (SR 291; IPRG) vor (<ref-law>), womit sich die Anerkennung des ausländischen Urteils und dessen Vollstreckung nach diesem Abkommen richten (Art. 26 ff und Art. 32 ff LugÜ). Wird auf dem Weg der Betreibung um Vollstreckung des ausländischen Urteils ersucht (Art. 32 Nr. 1 LugÜ), prüft der Rechtsöffnungsrichter vorfrageweise, ob das ausländische Urteil anerkannt werden kann (vgl. <ref-law>; AMONN/ WALTHER, Grundriss des Schuldbetreibungs- und Konkursrechts, 8. Aufl. 2008, § 19 Rz. 28 S. 146; Urteil 5P.275/2002 vom 20. November 2002 E. 2,3).
2.2 Nach <ref-law> hat die Partei, welche die Zwangsvollstreckung betreiben will, die Urkunden vorzulegen, aus denen sich ergibt, dass die Entscheidung nach dem Recht des Ursprungsstaats vollstreckbar ist und dass sie zugestellt worden ist. Das Zustellungserfordernis bezweckt, dass der Schuldner vor Einleitung des Vollstreckungsverfahrens von dem gegen ihn ergangenen Urteil Kenntnis erhalten und somit die Gelegenheit gehabt hat, ihm freiwillig nachzukommen (YVES DONZALLAZ, La Convention de Lugano, Band II, 1997, N. 3746 ff.; JAN KROPHOLLER, Europäisches Zivilprozessrecht, 6. Aufl., 1998, N. 3 zu Art. 47 EuGVÜ und LugÜ). Sowohl die Rechtswirksamkeit der Zustellung als auch die Art des Nachweises richten sich nach dem Recht des Urteilsstaates, einschliesslich der in diesem Staat anwendbaren Staatsverträge (KROPHOLLER, a.a.O., N. 5 zu Art. 47 EuGVÜ und LugÜ), im vorliegenden Fall nach dem HZÜ65.
2.3 Gemäss Art. 5 Abs. 1 HZÜ65 wird die Zustellung des Schriftstücks von der zentralen Behörde des ersuchten Staates bewirkt oder veranlasst, und zwar entweder in einer der Formen, die das Recht des ersuchten Staates für die Zustellung der in seinem Hoheitsgebiet ausgestellten Schriftstücke an dort befindliche Personen vorschreibt (Abs. 1 lit. a) oder in einer besonderen, von der ersuchenden Stelle gewünschten Form, es sei denn, diese Form sei mit dem Recht des ersuchten Staates unvereinbar (Abs. 1 lit. b). Von dem Fall des Absatzes 1 Buchstabe b abgesehen, darf die Zustellung stets durch einfache Übergabe des Schriftstücks an den Empfänger bewirkt werden, wenn er zur Annahme bereit ist (Art. 5 Abs. 2 HZÜ65).
Artikel 3 HZÜ65 zufolge richtet die nach dem Recht des Ursprungsstaats (Urteilsstaat) zuständige Behörde oder der nach diesem Recht zuständige Justizbeamte an die zentrale Behörde des ersuchten Staates ein Ersuchen, das dem diesem Übereinkommen als Anhang beigefügten Muster entspricht. Ist die zentrale Behörde der Ansicht, dass das Ersuchen nicht dem Übereinkommen entspricht, so unterrichtet sie unverzüglich die ersuchende Stelle und führt dabei die Einwände gegen das Ersuchen einzeln an (Art. 4 HZÜ65).
Nach Art. 6 HZÜ65 stellt die zentrale Behörde des ersuchten Staates oder jede von diesem hierzu bestimmte Behörde ein Zustellungszeugnis aus, das dem HZÜ65 als Anhang beigefügten Muster entspricht. Das Zeugnis enthält die Angaben über die Erledigung des Ersuchens; in ihm sind Form, Ort und Zeit der Erledigung sowie die Person anzugeben, der das Schriftstück übergeben worden ist. Gegebenenfalls sind die Umstände anzuführen, welche die Erledigung verhindert haben.
3. 3.1 Im vorliegenden Fall ist umstritten, ob die Zustellung des Urteils des Arbeitsgerichts Koblenz vom 8. Mai 2008 an die Beschwerdegegnerin den Anforderungen von <ref-law> bzw. Art. 6 HZÜ65 entsprechend nachgewiesen worden ist. Nach den Ausführungen des angefochtenen Beschlusses ist aktenkundig, dass als Zustellungszeugnis das Musterformular gemäss HZÜ65 (Anhang zum Abkommen) verwendet worden ist. Erstellt ist in tatsächlicher Hinsicht ebenso, dass die vorgedruckten Teile für Namen und Stellung der das Schriftstück entgegennehmenden Person sowie deren Verhältnis zur Zustellungsempfängerin nicht ausgefüllt worden sind. Das Obergericht leitet daraus ab, aufgrund der nach Art. 6 HZÜ65 erforderlichen, hier aber fehlenden Angaben mit Bezug auf die das Schriftstück entgegennehmenden Person könne nicht überprüft werden, ob die Zustellung ordnungsgemäss erfolgt sei. Damit sei die ordnungsgemässe Zustellung des zu vollstreckenden Urteils nicht <ref-law> bzw. Art. 6 HZÜ65 entsprechend nachgewiesen, sodass dem Rechtsöffnungsbegehren nicht entsprochen werden könne.
Fraglich sei überdies, so die Vorinstanz, ob die Angaben im Zustellungszeugnis zum Inhalt der Sendung den Anforderungen von Art. 6 HZÜ65 genügen, zumal darin nicht angegeben werde, um welche Art von Schriftstück es sich handelt. Im Zustellungszeugnis finde sich lediglich der allgemeine Hinweis, wonach das Zertifikat die Übergabe/Nichtübergabe aller Dokumente unter anderem in der Geschäftsnummer 7 Ca 2181/07, dem Aktenzeichen des fraglichen Verfahrens vor dem Arbeitsgericht Koblenz, bestätige. Aus dem Zustellungszeugnis gehe somit nicht hervor, ob es sich beim zugestellten Schriftstück tatsächlich um den fraglichen Entscheid des Arbeitsgerichts handle oder ob sich der Hinweis auf die spätere Retournierung von Einlegerakten beziehe.
Der Beschwerdeführer macht im Wesentlichen geltend, er habe mit dem Rechtsöffnungsbegehren das vom Obergericht des Kantons Zürich ausgestellte Zustellungszeugnis nach HZÜ65 eingereicht, wonach das Urteil des Arbeitsgerichts Koblenz der Beschwerdegegnerin am 27. August 2008 zugestellt worden ist. Im Weiteren werde auf dem Urteil dessen Vollstreckbarkeit bestätigt. Überhaupt scheine fraglich, ob der Nachweis der Zustellung nur mit dem Musterformular erfolgen könne. Selbst wenn dies zutreffe, seien genaue Angaben zur Person, die das Schriftstück entgegengenommen habe, nicht unerlässlich. Er vertritt damit im Ergebnis die Ansicht, das Zustellungszeugnis entspreche den Anforderungen von <ref-law> und Art. 6 HZÜ65.
Die Beschwerdegegnerin erachtet die Beschwerde als nicht den Anforderungen von <ref-law> entsprechend begründet und folglich unzulässig. Im Übrigen folgt sie mit Bezug auf die Anforderungen an das Zustellungszeugnis den Ausführungen des Obergerichts und ist nach wie vor der Ansicht, mit dem unvollständigen Zustellungszeugnis sei die ordnungsgemässe Zustellung des Urteils nicht nachgewiesen. Dieser Mangel könne auch nicht mit der auf dem untauglichen Zustellungszeugnis basierenden Bestätigung des Arbeitsgerichts geheilt werden, wonach das Urteil vollstreckbar sei.
3.2 Entgegen der Auffassung der Beschwerdegegnerin erweist sich die Beschwerde als den Anforderungen von <ref-law> entsprechend begründet. Die Eingabe des Beschwerdeführers setzt sich mit dem angefochtenen Beschluss auseinander (<ref-ruling>). Ihr lässt sich mit genügender Deutlichkeit entnehmen, dass der Beschwerdeführer mit der obergerichtlichen Auffassung betreffend den notwendigen Inhalt des Zustellungszeugnisses nicht einverstanden ist. Insbesondere hält er ausdrücklich dafür, die Bezeichnung der Person sei nicht unbedingt erforderlich.
3.3 Das Obergericht ist der Ansicht, das fragliche Zustellungszeugnis könne nicht als Grundlage für die Anerkennung dienen, da es weder Angaben zu den Personalien der das Urteil entgegennehmenden Person noch über deren Verhältnis zur Zustellungsempfängerin (Adressatin) enthalte, sodass die ordnungsgemässe Zustellung nicht überprüft werden könne.
3.3.1 Leistet die ersuchende Behörde einem mangelhaften Gesuch um Zustellung eines gerichtlichen Schriftstücks dennoch Folge, so kann aus dem mangelhaften Ersuchen nicht auf eine ungültige Zustellung geschlossen werden (<ref-ruling> E. 3.1). Eine Rückweisung des Zustellungsersuchens in Anwendung von Art. 4 HZÜ65 ist nur angezeigt, wenn die ausgewiesenen formellen Mängel nach Ansicht der ersuchten Behörde eine Zustellung einstweilen verunmöglichen (<ref-ruling> E. 3.1 S. 356). Nach der Lehre rechtfertigt sich eine Rückweisung eines Zustellungsersuchens auch nicht, wenn dieses nicht unbedingt dem ersten und zweiten Teil des Musterformulars entspricht (Thomas Bischof, Die Zustellung im internationalen Rechtsverkehr in Zivil- und Handelssachen, Diss. St. Gallen 1997, S. 280). Mit Bezug auf das Ersuchen um Zustellung eines gerichtlichen Schriftstücks sieht das dem Übereinkommen angefügte Muster des Formulars (vgl. E. 2.3) nicht vor, dass bei juristischen Personen Angaben zur vertretungsberechtigten Person zu machen sind. Nach Auffassung der Lehre ist es in erster Linie Aufgabe der zentralen Behörde, die für die Zustellung der Urkunde zweckdienlichen Angaben durch Einsicht in das Handelsregister zu ermitteln, vorausgesetzt, der Staat des Adressaten habe die Angabe solcher Spezifizierungen verlangt. In der Praxis werden denn auch Schriftstücke direkt an die juristische Person zugestellt (Peter F. Schlosser, EU-Zivilprozessrecht, 3. Aufl. 2009 N. 3 zu Art. 3 HZÜ65).
3.3.2 Im vorliegenden Fall ist nicht erstellt, dass der Staat des Adressaten genaue Angaben zur Person, die das Schriftstück entgegengenommen hat, sowie über die Stellung dieser Person bei der Beschwerdegegnerin verlangt hat. Aus dem Zustellungszeugnis ergibt sich unmissverständlich, dass das Schriftstück an die Sitzadresse der Beschwerdegegnerin zugestellt und von einer Person an dieser Adresse entgegengenommen worden ist. Im Lichte der bisherigen Ausführungen gilt der Nachweis der Zustellung als erbracht.
3.4 Nach Ansicht der Beschwerdegegnerin und des Obergerichts ist schliesslich fraglich, ob die Angaben im Zustellungszeugnis zum Inhalt der Sendung den Anforderungen von Art. 6 HZÜ65 genügen, zumal darin nicht angegeben wird, um welche Art von Schriftstück es sich handelt. Weder das Ersuchen noch das Zustellungszeugnis enthalten eine Rubrik, wonach anzugeben wäre, um welche Art von Schriftstück es sich handelt. Das Ersuchen spricht lediglich vom "Verzeichnis der Schriftstücke" bzw. von "Enumération des pièces". Im Zustellungszeugnis ist von "in dem Ersuchen erwähnten Schriftstücken" bzw. von "les documents mentionnés dans la demande" die Rede. Der Beschwerdeführer hatte bereits vor den kantonalen Instanzen das in der Sache ausgestellte Zustellungszeugnis ins Recht gelegt, wonach das Schriftstück mit der Referenz "7 Ca 2181/07" der Beschwerdegegnerin zugestellt worden ist. Diese im Zustellungszeugnis nur einmal verwendete Referenz ist unverwechselbar dem Urteil des Arbeitsgerichts Koblenz vom 8. Mai 2008 zuzuordnen, welches als Rechtsöffnungstitel im strittigen Rechtsöffnungsverfahren dient. Überdies wird in der eigens dafür vorgesehenen Rubrik "2" des Zustellungszeugnisses nicht erwähnt, dass die Zustellung in Form der einfachen Übergabe - etwa wegen Verweigerung der Annahme der Sendung - nicht hat vorgenommen werden können. Entgegen der Auffassung des Obergerichts und der Beschwerdegegnerin enthält das Zustellungszeugnis demnach die erforderlichen Anhaben mit Bezug auf das massgebende Schriftstück. Mit seiner gegenteiligen Auffassung hat das Obergericht <ref-law> und Art. 6 HZÜ65 verletzt.
4. Der erstinstanzliche Rechtsöffnungsrichter hat in seiner Verfügung vom 18. August 2009 nebst der Frage der genügenden Vollständigkeit der Angaben im Zustellungszeugnis noch eine weitere Anerkennungsvoraussetzung geprüft und ist der Frage nachgegangen, ob es sich bei der Betreibungsschuldnerin und der im Urteil des Arbeitsgerichts Koblenz aufgeführten Beklagten um ein und dieselbe Person handelt. Das Obergericht hat sich zu dieser Frage nicht geäussert und hat insbesondere keine für deren Beantwortung vorausgesetzten tatsächlichen Feststellungen getroffen. Damit ist das Bundesgericht zurzeit nicht in der Lage, sich zu diesem Verweigerungsgrund abschliessend zu äussern (<ref-law>; Urteil 4D_48/2007 vom 13. November 2007 E. 1.1; vgl. <ref-ruling> E. 3.1 mit Hinweisen). Die Sache ist somit auch zur Prüfung der von der Beschwerdegegnerin im kantonalen Rekursverfahren geltend gemachten weiteren Anerkennungsverweigerungsgründe an die Vorinstanz zurückzuweisen.
5. Da der Ausgang des Verfahrens noch offen ist, werden der einschlägigen Praxis entsprechend die Gerichtskosten beiden Parteien zur Hälfte auferlegt und die Parteientschädigungen wettgeschlagen (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Der Beschluss des Obergerichts des Kantons Zürich, II. Zivilkammer, vom 21. Januar 2010 wird aufgehoben und die Sache im Sinn der Erwägungen an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Parteien je zur Hälfte auferlegt.
3. Die Parteikosten werden wettgeschlagen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 7. Januar 2011
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zbinden