Sachverhalt:
A. In der von der Bank Y._ (Y._) gegen X._ über Fr. 775'834.30 nebst Zins zu 8,19% seit 12. März 2004 eingeleiteten Betreibung Nr. 1 versuchte das Betreibungsamt A._ am 7., 14. und 23. Januar 2008 erfolglos, den am 21. Dezember 2007 ausgefertigten Zahlungsbefehl in B._ zuzustellen.
Mit Schreiben vom 31. Januar 2008 informierte X._ das Betreibungsamt, dass er aus beruflichen Gründen am 17. November 2007 nach C._ (Deutschland) gezogen sei und nunmehr seinen ständigen Wohnsitz dort an der Strasse D._ habe.
Darauf veranlasste das Betreibungsamt die rechtshilfeweise Zustellung des Zahlungsbefehls, der am 28. Februar bzw. 3. März 2008 in C._ zugestellt wurde.
B. Am 6. März 2008 erhob X._ Beschwerde gemäss Art. 17 SchKG mit dem Begehren um Feststellung der Nichtigkeit des Zahlungsbefehls, eventualiter um dessen Aufhebung.
Der Bezirksgerichtspräsident A._ als untere Aufsichtsbehörde wies die Beschwerde am 21. Juli 2008 ebenso ab wie das Kantonsgericht Schwyz als obere kantonale Aufsichtsbehörde am 4. Dezember 2008.
C. Gegen den Beschluss des Kantonsgerichts hat X._ am 5. Januar 2009 eine Beschwerde in Zivilsachen eingereicht mit den Begehren um dessen Aufhebung und Feststellung der Nichtigkeit des Zahlungsbefehls, eventualiter um dessen Aufhebung, subeventualiter um Rückweisung der Sache an das Kantonsgericht. Am 19. Mai 2009 liessen sich das Betreibungsamt und das Kantonsgericht vernehmen; Letzteres verlangte die Abweisung der Beschwerde, soweit darauf einzutreten sei. Mit Vernehmlassung vom 11. Juni 2009 verlangte Y._ die Abweisung der Beschwerde und die Bestätigung des angefochtenen Beschlusses.

Erwägungen:
1. Der Beschwerde in Zivilsachen unterliegen unabhängig vom Streitwert (Art. 74 Abs. 2 lit. c BGG) auch Entscheide der kantonalen Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen (Art. 72 Abs. 2 lit. a BGG). Auf die fristgerecht eingereichte Beschwerde des vor der oberen kantonalen Aufsichtsbehörde unterlegenen Beschwerdeführers kann grundsätzlich eingetreten werden.
Der Beschwerdeführer rügt in verschiedener Hinsicht willkürliche Sachverhaltsfeststellungen und Rechtsverletzungen. Während für die Sachverhaltsfeststellung das Rügeprinzip gilt (Art. 97 Abs. 1 i.V.m. Art. 106 Abs. 2 BGG), wendet das Bundesgericht das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG).
2. Das Kantonsgericht hat erwogen, der Beschwerdeführer habe seine für das Datum vom 17. November 2007 behauptete Wohnsitzverlegung nach C._ mit der Vorlage des dortigen Arbeitsvertrages und der per 13. November 2007 erfolgten Beförderung nicht genügend nachgewiesen, denn es würden Belege darüber fehlen, dass er seine Tätigkeit als Geschäftsführer auch tatsächlich in diesem Zeitpunkt aufgenommen habe, sei doch der Eintrag im Handelsregister als neuer Geschäftsführer erst am 28. Januar 2008 erfolgt; ohnehin begründe aber ein Stellenwechsel nicht zwingend einen Wohnsitzwechsel. Im Übrigen sei die Wohnung in B._ nicht eigentlich gekündigt, sondern per Januar 2008 auf die Mitmieterin der Wohnung in C._ überschrieben worden. Sodann sei die Hinterlegung der Schriften (Anmeldung in C._ am 22. Januar 2008; Abmeldung in F._ am 4. Februar 2008) nur ein Indiz für eine allfällige Wohnsitzverlegung; ausschlaggebend sei aber ohnehin, dass der Beschwerdeführer im Zeitpunkt der Ausstellung des Zahlungsbefehls am 21. Dezember 2007 noch in der Gemeinde F._ angemeldet gewesen sei.
3. Das Kantonsgericht ist davon ausgegangen, der massgebliche Zeitpunkt für die Wohnsitzbestimmung sei der 17. November 2007, für welchen der Beschwerdeführer die Wohnsitzverlegung behaupte, bzw. der 21. Dezember 2007, an welchem das Betreibungsamt den Zahlungsbefehl ausgestellt habe; in diesem Zeitpunkt sei der Beschwerdeführer aber noch in der Gemeinde F._ angemeldet gewesen.
In rechtlicher Hinsicht ist diesbezüglich zu bemerken, dass die Ausstellung (d.h. die Ausfertigung) des Zahlungsbefehls durch das Betreibungsamt im Sinn von Art. 69 Abs. 1 SchKG noch keine Betreibungshandlung ist, weil sie den Betreibenden seinem Ziel nicht näher bringt und nicht in die Rechtsstellung des Betriebenen eingreift; erst die Zustellung des Zahlungsbefehls ist eine anfechtbare Betreibungshandlung (<ref-ruling>; <ref-ruling> E. 2a) und das SchKG hält in Art. 38 Abs. 2 explizit fest, dass erst mit diesem Akt die Schuldbetreibung überhaupt beginnt. Entgegen der Auffassung des Kantonsgerichts ist somit weder der 17. November 2007 noch der 21. Dezember 2007 relevant (Ausfertigung des Zahlungsbefehls), sondern der 28. Februar bzw. 3. März 2008 (Zeitpunkt der Zustellung), als der Beschwerdeführer längst in F._ ab- und in C._ angemeldet war.
Wo die Schriften hinterlegt sind, ist zwar für sich genommen nicht massgebend, wohl aber ein wichtiges Indiz zur Wohnsitzbestimmung (<ref-ruling> E. 2c S. 56; Urteil 7B.174/2005, E. 4.2). Im Übrigen erwähnt das Kantonsgericht auch noch weitere zwischenzeitlich eingetretene Anhaltspunkte, namentlich den Handelsregistereintrag als Geschäftsführer in C._. Die Wohnsitzfrage ist deshalb in tatsächlicher Hinsicht neu zu überprüfen, wofür der angefochtene Entscheid aufzuheben und die Sache an das Kantonsgericht zurückzuweisen ist.
4. Mit Blick auf den neu zu treffenden Entscheid sei das Kantonsgericht schliesslich auf die massgebende Rechtslage im Zusammenhang mit der Zustellung von Zahlungsbefehlen hingewiesen:
Hat der Beschwerdeführer im Zeitpunkt der Zustellung des Zahlungsbefehls seinen Wohnsitz in Deutschland, so ist die Einleitung der Betreibung in der Schweiz wegen fehlenden Betreibungsortes selbstredend nicht möglich (SCHMID, Basler Kommentar, N. 6 zu Art. 46 SchKG). Nur bei Vorliegen eines (hier offensichtlich nicht gegebenen) objektiven Anknüpfungspunktes - etwa bei der gelegenen Sache (Art. 51 Abs. 2 SchKG), aufgrund eines Spezialdomizils (Art. 50 Abs. 2 SchKG) oder infolge Prosequierung eines Ausländerarrestes (Art. 271 Abs. 1 Ziff. 4 SchKG) - wäre ein Betreibungsort gegeben und kann es bei einem Schuldner mit Wohnsitz im Ausland zu einer Betreibung in der Schweiz kommen.
Hat der Beschwerdeführer demgegenüber in der Schweiz Wohnsitz, gelten für die Zustellung des Zahlungsbefehls die Art. 71 f. SchKG sowie die allgemeinen Vorschriften von Art. 64 ff. SchKG über die Zustellung von Betreibungsurkunden. Gemäss Art. 64 SchKG werden Betreibungsurkunden dem Schuldner in seiner Wohnung oder am Ort seiner Berufsausübung zugestellt, bei Abwesenheit auch durch Aushändigung an eine zu seiner Haushaltung gehörende erwachsene Person oder an einen Angestellten; subsidiär erfolgt die Zustellung durch die Polizei. Ist die Zustellung auf diesem Weg nicht möglich, namentlich wegen - vorliegend nicht gegebenen - unbekannten Aufenthaltes des Schuldners, wird sie durch öffentliche Bekanntmachung ersetzt (Art. 66 Abs. 4 SchKG). Eine rechtshilfeweise Zustellung von Betreibungsurkunden im Ausland gemäss Art. 66 Abs. 3 SchKG - so wie sie vorliegend erfolgte - ist nur möglich, wenn der Schuldner tatsächlich am betreffenden Ort wohnt (vgl. ANGST, Basler Kommentar, N. 13 zu Art. 66; JEANNERET/LEMBO, Commentaire romand, N. 12 zu Art. 66; AMONN/WALTHER, Grundriss des Schuldbetreibungs- und Konkursrechts, 8. Aufl., § 12 N. 20). Diesfalls wäre aber die Einleitung der Betreibung in der Schweiz nach dem Gesagten unzulässig. Art. 66 Abs. 3 SchKG schafft keinen Betreibungsort in der Schweiz (SCHMID, Basler Kommentar, N. 9 zu Art. 46 SchKG), sondern regelt die Zustellung von Betreibungsurkunden, wenn in der Schweiz aus einem der in Art. 46 ff. SchKG geregelten Gründen ein Betreibungsort in der Schweiz gegeben ist, aber der Schuldner im Ausland wohnt, oder wenn er nach Ankündigung der Pfändung oder Zustellung der Konkursandrohung seinen Wohnsitz ins Ausland verlegt hat (vgl. Art. 53 SchKG) und weitere Betreibungsurkunden zuzustellen sind.
5. Der Beschwerdeführer ist im Grundsatz durchgedrungen, so dass die auf Beschwerdeabweisung schliessende Y._ kosten- und entschädigungspflichtig wird (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. In Gutheissung des Subeventualbegehrens wird der Beschluss des Kantonsgerichts Schwyz vom 4. Dezember 2008 aufgehoben und die Sache zur neuen Beurteilung im Sinn der Erwägungen an das Kantonsgericht zurückgewiesen.
2. Die Gerichtskosten von Fr. 5'000.-- werden der Bank Y._ auferlegt.
3. Die Bank Y._ hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 6'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Kantonsgericht des Kantons Schwyz, 2. Rekurskammer, als obere kantonale Aufsichtsbehörde in Schuldbetreibung und Konkurs, schriftlich mitgeteilt.
Lausanne, 9. Juli 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Möckli