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.