Die Kammer zieht in Erwägung:
1. In der von der Y._ AG gegen die Kollektivgesellschaft Z1._ in B._ eingeleiteten Betreibung Nr. xxxx erliess das Betreibungsamt B._ am 18. November 2004 die Konkursandrohung. Als an J._ (_strasse, DE-_ S._) adressierte eingeschriebene Sendung gab es die Urkunde am 22. November 2004 bei der Poststelle C._ auf. Sie wurde von der Adressatin am 24. November 2004 in Empfang genommen.
Mit einer vom 3. Dezember 2004 datierten Eingabe erhob die Kollektivgesellschaft Z._ beim Gerichtspräsidium Kreuzlingen als unterer Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen Beschwerde gegen die Konkursandrohung und machte geltend, das Betreibungsamt B._ sei örtlich nicht zuständig, weil die Z1._ keinen Sitz im Kanton Thurgau (mehr) habe.
Der Vizepräsident des Bezirksgerichts Kreuzlingen wies die Beschwerde am 20. Dezember 2004 ab.
Die von der Z._ hiergegen eingereichte Beschwerde wies das Obergericht des Kantons Thurgau als (obere) kantonale Aufsichtsbehörde am 27. Januar 2005 ab, soweit es darauf eintrat.
Die Z._ nahm diesen Beschluss am 16. Februar 2005 in Empfang. Mit einer vom 26. Februar 2005 datierten und am 28. Februar 2005 (Montag) zur Post gebrachten Eingabe führt sie (rechtzeitig) Beschwerde an die Schuldbetreibungs- und Konkurskammer des Bundesgerichts und verlangt (dem Sinne nach), die Konkursandrohung aufzuheben bzw. festzustellen, dass deren Zustellung nichtig sei.
Die kantonale Aufsichtsbehörde hat sich zur Beschwerde nicht geäussert.
Das Betreibungsamt B._ schliesst auf Abweisung der Beschwerde, und die Beschwerdegegnerin Y._ AG beantragt, auf die Beschwerde nicht einzutreten, sie allenfalls abzuweisen.
2. Die Beschwerdeführerin rügt, dass die Konkursandrohung in Deutschland am Wohnsitz des einen Gesellschafters in S._ (direkt postalisch) zugestellt worden sei, was mangels eines entsprechenden Rechtshilfeabkommens unzulässig gewesen sei; die Zustellung sei daher nichtig.
2.1 Wie die erkennende Kammer in <ref-ruling> (E. 4 S. 42) - im Falle einer Zustellung nach Italien - entschieden hat, ist die (direkte) postalische Zustellung einer Betreibungsurkunde nach dem Ausland schlechthin nichtig, wenn sie in Verletzung staatsvertraglicher Bestimmungen vorgenommen wurde. Die Nichtigkeit einer Betreibungshandlung ist - von hier nicht in Betracht fallenden Ausnahmen aus Gründen des zu schützenden guten Glaubens abgesehen (dazu Franco Lorandi, Betreibungsrechtliche Beschwerde und Nichtigkeit, Basel 2000, N. 176 f. zu Art. 22 SchKG) - jederzeit zu beachten und von Amtes wegen festzustellen (vgl. Art. 22 Abs. 1 SchKG; <ref-ruling> E. 2 S. 144 mit Hinweis). Auf die gegen die Form der Zustellung der Konkursandrohung erhobene Rüge ist hier daher einzutreten.
2.2 Für die Zustellung von Betreibungsurkunden ins Ausland ist grundsätzlich die Vermittlung der dortigen Behörden in Anspruch zu nehmen; soweit völkerrechtliche Verträge dies vorsehen oder wenn der Empfängerstaat zustimmt, kann auch durch die Post zugestellt werden (Art. 66 Abs. 3 SchKG).
2.2.1 Im internationalen Verhältnis bestimmt sich die Zustellung von Betreibungsurkunden im Allgemeinen nach dem Haager Übereinkommen vom 15. November 1965 über die Zustellung gerichtlicher und aussergerichtlicher Schriftstücke im Ausland in Zivil- und Handelssachen (SR 0.274.131; <ref-ruling> E. 2a S. 396), das für Deutschland am 26. Juni 1979 und für die Schweiz am 1. Januar 1995 in Kraft trat. Darnach sind die Schriftstücke grundsätzlich durch Vermittlung der von jedem Vertragsstaat zu bestimmenden zentralen Behörde zuzustellen (Art. 2 bis 6). Unter dem Vorbehalt, dass der Bestimmungsstaat keinen Widerspruch erklärt, sieht Art. 10 des Übereinkommens freilich vor, dass gerichtliche Schriftstücke unter anderem auch unmittelbar durch die Post übersandt werden dürfen (lit. a). Wie die Schweiz (in Ziff. 5 ihrer Vorbehalte) hat Deutschland indessen (in Ziff. 4 Abs. 2 seiner Vorbehalte) ausdrücklich erklärt, dass eine Zustellung nach Art. 10 des Übereinkommens nicht stattfindet (dazu Reinhold Geimer, Internationales Zivilprozessrecht, 5. Auflage, Köln 2005, S. 640, Rz. 2084, und S. 677, Rz. 2176). Die strittige Zustellung der Konkursandrohung verstösst mithin gegen das einschlägige Haager Übereinkommen.
2.2.2 Angesichts des konkreten Bestimmungsortes drängt sich die Frage auf, ob die (direkte) postalische Zustellung allenfalls auf Grund eines der bezüglich Deutschland territorial begrenzten Staatsverträge zulässig gewesen sei. S._ liegt im Bundesland Baden-Württemberg und gehörte früher zum Grossherzogtum Baden bzw. zum Land Baden, das seit 1952 Teil des neu gebildeten Landes Baden-Württemberg ist (dazu die Stellungnahme vom 16. Februar 1988 des Ministeriums für Justiz, Bundes- und Europaangelegenheiten von Baden-Württemberg, [auszugsweise] wiedergegeben bei Erich Bürgi, Konkursrechtliche Staatsverträge der Schweiz, insbesondere mit den ehemaligen Königreichen Württemberg und Bayern sowie mit Frankreich, in: Festschrift 100 Jahre SchKG, Zürich 1989, S. 175 ff., insbes. S. 179, und in: BlSchK 53/1989, S. 81 ff., insbes. S. 86 f.).
Ein am 9. Juli 1808 vom Landammann der Schweiz namens der damaligen Kantone (mit Ausnahme von Schwyz und Glarus) mit dem Grossherzogtum Baden geschlossener Vertrag betreffend die Gleichstellung beiderseitiger Staatsbürger in Konkursfällen wurde auf Wunsch von Baden auf den 1. Januar 1903 ausser Kraft gesetzt (dazu Lucas David, In Vergessenheit geratene Staatsverträge, in: SJZ 69/1973, S. 84).
Zwischen der Schweizerischen Eidgenossenschaft und der Krone Württemberg wurde alsdann unter den Daten vom 12. Dezember 1825 und 13. Mai 1826 die Übereinkunft "betreffend die Konkursverhältnisse und gleiche Behandlung der beiderseitigen Staatsangehörigen in Konkursfällen (Konkursvertrag)" geschlossen (abgedruckt bei Hans Ulrich Walder, Schuldbetreibung und Konkurs, 16. Auflage, Zürich 2002, S. 970 f.). Nach deren Art. I wurde gegenseitig die "Allgemeinheit des Konkursstandes in dem Wohnorte des Gemeinschuldners" anerkannt. Dass das Abkommen nach wie vor gilt, ist schweizerischerseits auch nach der Ablösung des Staatenbundes durch den Bundesstaat nie bezweifelt worden (vgl. David, a.a.O., S. 85; Paul Volken, in: Zürcher Kommentar zum IPRG, Zürich 2004, Rz. 71 und 73 vor Art. 166-175). Ebenso ist das Ministerium für Justiz, Bundes- und Europaangelegenheiten von Baden-Württemberg in seiner bereits erwähnten Stellungnahme davon ausgegangen, die Übereinkunft stehe nach wie vor in Kraft. In territorialer Hinsicht hielt es allerdings dafür, dass es nur im Gebiet des früheren Königreichs Württemberg (mit Einschluss der ehemaligen Hohenzollerschen Lande) Anwendung finde, das den Vertrag abgeschlossen habe, und dass der Zusammenschluss der Länder Württemberg-Baden, Württemberg-Hohenzollern und (Süd-)Baden (in dem S._ gelegen war) im Jahre 1952 nicht zu einer Ausdehnung des Geltungsbereichs geführt habe (vgl. Bürgi, in: Festschrift 100 Jahre SchKG, S. 179, und in: BlSchK 53/1989, S. 86 f.).
2.2.3 Nach dem Gesagten bleibt es bei der Feststellung, dass die (direkte) postalische Zustellung der Konkursandrohung gegen staatsvertragliche Bestimmungen verstiess. Sie ist daher nichtig. Auf Grund der Erklärung vom 1./13. Dezember 1878 zwischen der Schweiz und dem Deutschen Reiche betreffend den unmittelbaren Geschäftsverkehr zwischen den beiderseitigen Gerichtsbehörden (SR 0.274.181.361) und Art. 1 der Erklärung vom 30. April 1910 zwischen der Schweiz und Deutschland betreffend Vereinfachung des Rechtshilfeverkehrs (SR 0.274.181.362) hätte das Betreibungsamt B._ (direkt) das für S._ zuständige Amtsgericht Waldshut-Tiengen um die Zustellung der Konkursandrohung ersuchen müssen (vgl. <ref-ruling> E. 3 S. 13).

Demnach erkennt die Kammer:
1. Soweit auf die Beschwerde einzutreten ist, wird sie gutgeheissen, und es wird festgestellt, dass die (direkte) postalische Zustellung der am 18. November 2004 in der Betreibung Nr. xxxx gegen die Kollektivgesellschaft Z1._ in B._ erlassene Konkursandrohung durch das Betreibungsamt B._ an J._ in S._ (Deutschland) nichtig ist.
2. Dieses Urteil wird der Beschwerdeführerin, der Beschwerdegegnerin Y._ AG, vertreten durch Rechtsanwalt Dr. Remi Kaufmann, dem Betreibungsamt B._ und dem Obergericht des Kantons Thurgau als (oberer) kantonaler Aufsichtsbehörde über Schuldbetreibung und Konkurs schriftlich mitgeteilt.
Lausanne, 15. Juni 2005
Im Namen der Schuldbetreibungs- und Konkurskammer
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber: