Aus den Erwägungen:
5.1. Das LugÜ regelt die Vollstreckung der in einem andern Vertragsstaat ergangenen Entscheidungen in den Art. 31-45. Geltung haben auch die "gemeinsamen Vorschriften" gemäss Art. 46-49 LugÜ. Wer eine Entscheidung in einem andern Vertragsstaat zwangsvollstrecken will, hat gemäss Art. 33 Abs. 3 LugÜ seinem Antrag die in den Art. 46 und 47 angeführten Urkunden beizufügen. So hat die ersuchende Partei nach Art. 47 Ziff. 1 LugÜ die Urkunden vorzulegen, aus denen sich ergibt, dass die Entscheidung nach dem Recht des Ursprungsstaates vollstreckbar ist und dass sie zugestellt worden ist. Die Art der Zustellung richtet sich nach dem Recht des Urteilsstaates (Kropholler, a.a.O., N 5 zu Art. 47 EuGVÜ/LugÜ), hier nach deutschem Recht. Entgegen der Auffassung der Vorinstanz kommt vorliegend nicht das Haager Übereinkommen über die Zustellung gerichtlicher und aussergerichtlicher Schriftstücke im Ausland in Zivil- oder Handelssachen vom 15. November 1965 (SR 0.274.131) zur Anwendung. Das Mahnverfahren, das dem Vollstreckungsbescheid vom 30. November 1995 zugrunde liegt, wurde auf Antrag der Klägerin in Deutschland gegen den Beklagten durchgeführt, der unbestritten bis Ende Dezember 1995 Wohnsitz in Deutschland hatte. Es geht somit nicht um die Zustellung eines gerichtlichen Schriftstückes im Ausland nach dem Haager Zustellungsübereinkommen, sondern um die Zustellung des Vollstreckungsbescheids nach deutschem Prozessrecht. Deren Ordnungsmässigkeit ist im Folgenden zu prüfen.
5.2. Nach § 699 Abs. 4 DZPO wird der Vollstreckungsbescheid dem Antragsgegner grundsätzlich von Amtes wegen zugestellt. Der Urkundsbeamte der Geschäftsstelle desjenigen Gerichts, das den Vollstreckungsbescheid erlassen hat, hat die Zustellung unverzüglich zu veranlassen. Der Antragsteller erhält eine mit der Zustellungsbescheinigung versehene Ausfertigung, die ihm die Zwangsvollstreckung ermöglicht (Baumbach/Lauterbach/Albers/Hartmann, Zivilprozessordnung, 53. Aufl., München 1995, § 699 Rdn 18). Der von der Klägerin aufgelegte Vollstreckungsbescheid vom 30. November 1995 in der Ausfertigung für den Antragsteller enthält folgenden Vermerk: "Dieser Bescheid wurde dem Antragsgegner zugestellt am 4.12.1995. Hagen, den 11.12.1995." Dabei handelt es sich offensichtlich um die oben erwähnte Zustellungsbescheinigung auf dem für den Antragsteller bestimmten Exemplar des Vollstreckungsbescheids. Im Rekursverfahren legt die Klägerin zudem neu ein Schreiben des Amtsgerichts München vom 10. Mai 1999 auf, worin ihr mitgeteilt wird, dass der Vollstreckungsbescheid vom 30. November 1995 dem Beklagten am 4. Dezember 1995 durch Niederlegung unter der Adresse Webergasse 14 in 83671 Benediktbeuren zugestellt wurde. Gemeint ist damit offensichtlich die Ersatzzustellung durch Niederlegung gemäss § 182 DZPO, die zum Zuge kommt, wenn eine Übergabe an den Adressaten oder an Hausgenossen, Hauswirt oder Vermieter nicht möglich ist. In diesem Fall kann die Zustellung dadurch erfolgen, dass das zu übergebende Schriftstück auf der Geschäftsstelle des Amtsgerichts, in dessen Bezirk der Ort der Zustellung gelegen ist, oder an diesem Ort bei der Postanstalt oder dem Gemeindevorsteher oder dem Polizeivorsteher niedergelegt und eine schriftliche Mitteilung über die Niederlegung unter der Anschrift des Empfängers in der bei gewöhnlichen Briefen üblichen Weise abgegeben oder, falls dies nicht tunlich ist, an die Tür der Wohnung befestigt oder einer in der Nachbarschaft wohnenden Person zur Weitergabe an den Empfänger ausgehändigt wird (vgl. Stein-Jonas, Komm. zur Zivilprozessordnung, N 1 zu § 182 DZPO; vgl. Bischof, Die Zustellung im internationalen Rechtsverkehr in Zivil- oder Handelssachen, Zürich 1997, S. 80 f.). Damit ist von der gültigen Zustellung des Vollstreckungsbescheids an den Beklagten in Deutschland auszugehen. Dass der Beklagte angeblich wegen einer Dienstreise an seinem Wohnsitz nicht angetroffen werden konnte, ist nach dem Gesagten ohne Bedeutung, erfolgt doch in diesem Fall die Zustellung durch Niederlegung im Sinne einer Ersatzzustellung. Eine unter dem Blickwinkel rechtsgenüglicher Zustellung gemäss Art. 47 Ziff. 1 LugÜ nicht zu prüfende Frage ist, ob die Zustellung des Urteils im konkreten Fall gegen die öffentliche Ordnung verstösst (Art. 27 Ziff. 1 LugÜ; vgl. unveröffentlichtes Urteil des Bundesgerichts i.S. K.G. gegen J.H. vom 28.10.1997 S. 14; dies wäre im Übrigen zu verneinen: Staehelin, Die Anerkennung ausländischer Konkurse und Nachlassverträge in der Schweiz [Art. 166ff. IPRG], Basel und Frankfurt am Main 1989, S. 62f.). Dem Vollstreckungsrichter ist es nach Art. 28 Abs. 3 LugÜ grundsätzlich auch untersagt, die Zuständigkeit der Gerichte des Ursprungsstaates nachzuprüfen (BGE 123 III 377).
5.3. Weiter ist unzweifelhaft auch die Vollstreckbarkeit des Vollstreckungsbescheids nach deutschem Recht gegeben. Der Vollstreckungsbescheid verleiht dem ihm vorausgehenden Mahnbescheid die Vollstreckbarkeit, d.h. der Mahnbescheid bedarf, um Vollstreckungstitel und rechtskräftige Feststellung zu werden, des Eintritts seiner Bedingung durch den Vollstreckungsbescheid (Stein-Jonas, a.a.O., N 1 zu § 699 DZPO; vgl. Meier Isaak, Besondere Vollstreckungstitel nach dem Lugano-Übereinkommen, in: Schwander Ivo [Hrsg.], Das Lugano-Übereinkommen, St. Galler Studien zum internationalen Recht, St. Gallen 1990, S. 208). Er wurde denn auch nach der bisherigen bundesgerichtlichen Rechtsprechung als vollstreckungsfähiger Titel anerkannt (Kren Jolanta, a.a.O., S. 442 FN 113). Das Mahnverfahren des deutschen Zivilprozessrechts führt letztlich zu einer rechtskräftigen Feststellung der Forderung. Es soll dem Gläubiger einer wahrscheinlich unstreitigen Geldforderung schnell und einfach ohne mündliche Verhandlung einen Vollstreckungstitel verschaffen. Das Amtsgericht, bei dessen Rechtspfleger der Gläubiger den Erlass eines Mahnbescheids beantragt hat, nimmt lediglich eine formale Kontrolle vor und erlässt den Mahnbescheid ohne Prüfung, ob der Anspruch in der Sache begründet ist. Erhebt der Schuldner nach Erhalt des Mahnbescheids nicht rechtzeitig Widerspruch, erlässt das Gericht auf Antrag des Gläubigers einen Vollstreckungsbescheid, der einem für vorläufig vollstreckbar erklärten Versäumnisurteil gleichsteht (§ 699 f. DZPO; BGE 123 III 380). Bleibt der Vollstreckungsbescheid, wie vorliegend, ohne Einspruch, erwächst der geltend gemachte Anspruch in materielle Rechtskraft (Stein-Jonas, § 700 Rdn 10; Markus Alexander R., Lugano Übereinkommen und SchKG-Zuständigkeiten: Provisorische Rechtsöffnung, Aberkennungsklage und Zahlungsbefehl, Basel und Frankfurt am Main 1997, S. 113 f.). Demnach ist die Klägerin ihren Obliegenheiten gemäss Art. 47 Ziff. 1 LugÜ nachgekommen und es steht diesbezüglich einer Zwangsvollstreckung nichts entgegen.
5.4. Nach Art. 46 Ziff. 2 LugÜ hat die Partei, welche die Zwangsvollstreckung betreiben will, bei einer im Versäumnisverfahren ergangenen Entscheidung die Urschrift oder eine beglaubigte Abschrift der Urkunde vorzulegen, aus der sich ergibt, dass das den Rechtsstreit einleitende Schriftstück oder ein gleichwertiges Schriftstück der säumigen Partei zugestellt worden ist. Da der Vollstreckungsbescheid nach § 700 Abs. 1 DZPO ohne Anhörung des Schuldners erlassen wurde und einem Versäumnisurteil gleichsteht, ist die Bestimmung von Art. 46 Ziff. 2 LugÜ auch im vorliegenden Verfahren anzuwenden (Kropholler, a.a.O., N 3 zu Art. 46 EuGVÜ/
LugÜ). Das verfahrenseinleitende Schriftstück im Sinne von Art. 27 Ziff. 2 LugÜ ist die vom Recht des Urteilsstaates vorgesehene Urkunde, durch deren Zustellung der Beklagte erstmals von dem der Entscheidung zugrunde liegenden Verfahren Kenntnis erlangt. Es ist dasjenige Schriftstück, dessen ordnungsgemässe und rechtzeitige Zustellung den Beklagten in die Lage versetzt, seine Rechte vor Erlass einer vollstreckbaren Entscheidung im Urteilsstaat geltend zu machen (BGE 123 III 381). Der Mahnbescheid gemäss § 692 DZPO ist als verfahrenseinleitendes Schriftstück anzusehen, weil seine Zustellung an den Schuldner es dem Gläubiger ermöglicht, wenn dieser untätig bleibt und keinen Widerspruch erhebt, eine nach den Bestimmungen des Übereinkommens vollstreckbare Entscheidung zu erwirken (BGE 123 III 381; Kropholler, a.a.O., N 24 zu Art. 27 EuGVÜ/LugÜ; vgl. Markus, a.a.O., S. 159 ff. insbes. S. 162).
5.5. Gestützt auf Art. 48 Abs. 1 LugÜ, der einen übertriebenen Formalismus ausschliessen will (Kropholler, a.a.O., N 1 zu Art. 48 EuGVÜ/LugÜ), wurde die Klägerin aufgefordert, den am 7. November 1995 erlassenen und am 10. November 1995 zugestellten Mahnbescheid samt Zustellungsnachweis vorzulegen. Innert Frist reichte diese eine Urkunde des Amtsgerichts Hagen vom 16. November 1995 ein, die als "Zustellungsnachricht" bezeichnet ist und in welcher der Klägerin mitgeteilt wird, der Mahnbescheid sei am 10. November 1995 zugestellt worden. Damit ist der Nachweis der Zustellung des Mahnbescheids erbracht, was im Hinblick auf Art. 46 Ziff. 2 LugÜ genügt. Somit steht fest, dass der Vollstreckungsbescheid vom 30. November 1995 in der Schweiz vollstreckbar ist und der Klägerin gestützt darauf grundsätzlich die definitive Rechtsöffnung gewährt werden kann.