Sachverhalt: A. Der 1967 geborene deutsche Staatsangehörige L._ liess sich im September 2001 zur Aufnahme einer unselbstständigen Erwerbstätigkeit in der Schweiz nieder. Mit Schreiben vom 27. November 2001 befreite ihn die Gesundheitsdirektion des Kantons Zürich von der schweizerischen KVG-Versicherungspflicht, solange er bei der Krankenversicherung X._ in Deutschland versichert sei. Auf 31. August 2007 verlegte L._ seinen Wohnsitz in den Kanton Schwyz. Ordnungsgemäss füllte er ein neues Formular zur Abklärung der KVG-Versicherungspflicht aus (unterzeichnet am 31. August 2007) und hielt im Begleitschreiben vom 3. Oktober 2007 fest, er gehe davon aus, dass im Formular kein neues Gesuch um Befreiung von der Versicherungspflicht zu sehen sei, sondern es sich dabei um "eine Kenntnisnahme des bestehenden Sachverhaltes mit entsprechendem Bestandesschutz" handle. Die Ausgleichskasse Schwyz verfügte am 12. Oktober 2007, das Gesuch um Befreiung vom Schweizerischen KVG-Obligatorium werde abgelehnt, da sich aus den eingereichten Unterlagen kein Befreiungsgrund ergebe. Mit Einspracheentscheid vom 25. April 2008 bestätigte sie ihre Verfügung. B. Das Verwaltungsgericht des Kantons Schwyz wies die hiegegen erhobene Beschwerde des L._ mit Entscheid vom 23. September 2008 ab. C. L._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen. Er beantragt, unter Aufhebung des angefochtenen Entscheides sei die Nichtigkeit des Einspracheentscheides vom 25. April 2008 festzustellen und er sei weiterhin von der Versicherungspflicht zu befreien. Eventualiter sei die Sache zur erneuten Entscheidung an die zuständige Behörde zurückzuweisen. Die Ausgleichskasse lässt sich vernehmen, ohne einen Antrag zu stellen. Vorinstanz und Bundesamt für Gesundheit verzichten auf eine Stellungnahme. 