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.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>).
2. 2.1 Die Vorinstanz erwog, die Beschwerdegegnerin habe zwar das rechtliche Gehör des Beschwerdeführers verletzt, indem sie ihn nicht darauf hinwiesen habe, dass er nach seinem Wohnsitzwechsel, ungeachtet der im Jahre 2001 erfolgten Befreiung vom Versicherungsobligatorium, ein neues Gesuch hätte stellen müssen. Von einer Wiederholung des Verfahrens könne aber abgesehen werden, da der Beschwerdeführer im Einspracheverfahren eingehend begründet habe, aus welchen Gründen er vom Versicherungsobligatorium befreit werden wolle.
In materiellrechtlicher Hinsicht habe der Beschwerdeführer nicht dargelegt, dass eine Unterstellung unter die schweizerische Versicherung für ihn eine Verschlechterung des bisherigen Versicherungsschutzes oder der bisherigen Kostendeckung zur Folge hätte und aus welchen Gründen eine Zusatzversicherung im bisherigen Umfang für ihn unzumutbar sei. Damit seien die Befreiungsvoraussetzungen nicht erfüllt, woran auch das Schreiben der Gesundheitsdirektion des Kantons Zürich vom 27. November 2001 nichts zu ändern vermöge.
2.2 Der Beschwerdeführer rügt, zunächst hätte über ein auf <ref-law> gestütztes Gesuch nicht die beschwerdegegnerische Ausgleichskasse, sondern - wegen der Nähe zu europarechtlichen Fragestellungen - die Gemeinsame Einrichtung entscheiden müssen. Der Einspracheentscheid sei daher ohne weiteres nichtig. Wenn er sich im Einspracheverfahren "ergänzend" mit den Aspekten von <ref-law> auseinandergesetzt habe bedeute dies im Übrigen nicht, dass er das ihm zustehende rechtliche Gehör effektiv habe wahrnehmen können. Die Sache müsse daher an die Beschwerdegegnerin zurückgewiesen werden, damit diese ihm Gelegenheit einräume, den auf <ref-law> gestützten Sachverhalt zu belegen.
2.3 Auch inhaltlich sei der angefochtene Entscheid unhaltbar. Weil Übergangsbestimmungen zu <ref-law> insgesamt fehlten, könne das neue Recht auf abgeschlossene Sachverhalte keine Anwendung finden. Angesichts der Tragweite einer Neuunterstellung unter das schweizerische Versicherungsobligatorium für den Einzelnen hätte der Verordnungsgeber eine entsprechende Regelung vorsehen müssen. Weder in der Lehre noch in der Rechtsprechung werde denn auch die Ansicht vertreten, dass bereits befreite Personen nach Inkrafttreten der geänderten Bestimmung auf 1. Juni 2002 neu und erstmalig der schweizerischen Krankenversicherung obligatorisch unterstellt werden sollten. Die Zürcherischen Behörden hätten nach Inkrafttreten der neuen Bestimmung zu Recht keinen Anlass gesehen, den fraglichen Entscheid zu ändern. In Würdigung der seit der Befreiung vom Versicherungsobligatorium verstrichenen Zeit müsse von einer definitiv erworbenen Vertrauensposition ausgegangen werden. Der Wohnsitzwechsel ändere daran nichts; eine andere Betrachtungsweise verstiesse gegen die Niederlassungsfreiheit. Schliesslich verfüge der Beschwerdeführer bei der Krankenversicherung X._ in Deutschland über eine sehr umfassende Versicherungsdeckung, welche beispielsweise auch Zahnschäden vollständig abdecke. Aufgrund seines Alters von 40 Jahren im massgeblichen Zeitpunkt sei es zudem fraglich, ob er in der Schweiz ohne weiteres die entsprechende Versicherungsdeckung wieder erlangen könnte. Jedenfalls müsste er ausserordentlich hohe Prämien gewärtigen.
3. 3.1 Nach <ref-law> (in Kraft seit 1. Juni 2002) entscheidet die vom Kanton bezeichnete Behörde über Anträge um Befreiung von der Versicherungspflicht. Vorbehalten werden <ref-law>. Nach <ref-law> entscheidet die Gemeinsame Einrichtung über Anträge um Befreiung von der Versicherungspflicht von Rentnerinnen und Rentnern sowie deren Familienangehörigen, die in einem Mitgliedstaat der Europäischen Gemeinschaft, in Island oder in Norwegen wohnen. Abs. 2ter von <ref-law> gibt der Gemeinsamen Einrichtung die Befugnis, Rentnerinnen und Rentner sowie deren Familienangehörige, die ihrer Versicherungspflicht nicht rechtzeitig nachkommen, einem Versicherer zuzuweisen.
3.2 Die vom Beschwerdeführer vertretene Auffassung, wonach die Gemeinsame Einrichtung über Gesuche zu entscheiden hätte von Personen, für welche eine Unterstellung unter die schweizerische Versicherung eine klare Verschlechterung des bisherigen Versicherungsschutzes oder der bisherigen Kostendeckung zur Folge hätte und die sich auf Grund ihres Alters und/oder ihres Gesundheitszustandes nicht oder nur zu kaum tragbaren Bedingungen im bisherigen Umfang zusatzversichern könnten (<ref-law>), findet somit im Gesetzeswortlaut keine Stütze.
3.3 Soweit der Beschwerdeführer aus <ref-law> (e contrario) schliesst, dass die Gemeinsame Einrichtung für Gesuche nach <ref-law> zuständig sei, weil in <ref-law> die kantonale Behörde nur für die in den Art. 2 Abs. 2 bis 5 sowie <ref-law> vorgesehenen Gesuche als zuständig erklärt wird, kann ihm nicht gefolgt werden. Ohne dass weiter geprüft werden muss, ob der Verordnungsgeber in <ref-law> die Gesuche nach <ref-law> absichtlich nicht der zuständigen kantonalen Stelle zugeordnet hat oder ob es sich dabei um eine ungewollte Unvollständigkeit handelt, geht die Gesetzesbestimmung (<ref-law>) als höherstufige Norm der Verordnungsregelung jedenfalls vor ("lex superior derogat legi inferiori") und verdrängt diese auch deshalb, weil es sich bei ihr um die neuere Norm handelt ("lex posterior derogat legi priori"). Damit fällt der hier zu entscheidende Befreiungsfall nicht in die Zuständigkeit der Gemeinsamen Einrichtung gemäss Art. 18 Abs. 2bis in Verbindung mit <ref-law>, so dass die Ausgleichskasse als zuständige kantonale Behörde rechtmässig über das Gesuch des Beschwerdeführers entschieden hat (vgl. auch <ref-ruling>, wo ebenfalls die Ausgleichskasse entschied).
4. 4.1 Nach <ref-law> müssen die Parteien nicht angehört werden vor Verfügungen, die durch Einsprache anfechtbar sind. Während im Beschwerdeverfahren wegen der formellen Natur des rechtlichen Gehörs die in Verletzung dieses Anspruchs ergangene Verfügung (vorbehältlich einer Heilung) unabhängig von der materiellen Beurteilung aufgehoben werden muss, gilt dies für das Einspracheverfahren zum vornherein nicht. Es genügt, das rechtliche Gehör im Einspracheverfahren zu gewähren und gestützt darauf neu zu entscheiden (Hansjörg Seiler, Rechtsfragen des Einspracheverfahrens in der Sozialversicherung [<ref-law>], in: Schaffhauser/Schlauri, Sozialversicherungsrechtstagung 2007, St. Gallen 2007, S. 102 f.).
4.2 Davon abgesehen, dass der Beschwerdeführer in seiner Einsprache im Einzelnen dargelegt hat, weshalb er von der Versicherungspflicht zu befreien sei (insbesondere weil die in Deutschland abgeschlossene Versicherung "wesentlich grössere Bereiche" abdecke als eine Pflichtversicherung in der Schweiz und ein Ausscheiden aus der seit zwölf Jahren bestehenden Versicherung Nachteile zur Folge hätte, namentlich "den Verlust der bereits einbezahlten Altersprogression" sowie eine "unzumutbar höhere Franchise" bei späterem Wiedereinstieg), hatte ihm spätestens nach Kenntnisnahme des Einspracheentscheides vom 25. April 2008 klar sein müssen, dass die Beschwerdegegnerin die Befreiung vom Versicherungsobligatorium gestützt auf <ref-law> aus materiellen Gründen verweigerte. Er hätte sich somit im vorinstanzlichen Beschwerdeverfahren mit den entsprechenden Argumenten auseinandersetzen und Befreiungsgründe geltend machen können. Damit bestand ausreichend Gelegenheit, die Argumente in materieller Hinsicht vorzubringen. Die neuen Vorbringen des Beschwerdeführers, er könne wegen seines Alters (im massgeblichen Zeitpunkt: 40 Jahre) nicht ohne weiteres Zusatzversicherungen abschliessen und eine vergleichbare Deckung wäre in der Schweiz nicht oder jedenfalls nicht zu tragbaren Bedingungen möglich, sind letztinstanzlich nicht zu berücksichtigen (<ref-law>).
4.3 Im Übrigen wären im Lichte der Rechtsprechung die Befreiungsvoraussetzungen von <ref-law> selbst dann nicht erfüllt, wenn auf die Noven abgestellt würde. Mit Blick auf die gesetzgeberisch gewollte Solidarität zwischen Gesunden und Kranken sind die Ausnahmen von der Versicherungspflicht generell eng zu halten und es ist der Befürchtung des Gesetzgebers Rechnung zu tragen, dass sich das schweizerische Obligatorium unterlaufen liesse, wenn beispielsweise der Nachweis einer ausländischen freiwilligen privaten Versicherung allgemein als Befreiungsgrund akzeptiert würde (<ref-ruling> E. 8.5.6 S. 317). Für die Anwendung von <ref-law> sind daher strenge Massstäbe anzuwenden. Insbesondere darf diese Bestimmung nicht dazu dienen, blosse Nachteile zu verhindern, die eine Person dadurch erleidet, dass das schweizerische System den Versicherungsschutz, den sie bisher unter dem ausländischen System genoss, überhaupt nicht oder nicht zu gleich günstigen Bedingungen vorsieht. Vor diesem Hintergrund erfüllt der Beschwerdegegner allein wegen seines Alters die restriktiv zu handhabenden Befreiungsvoraussetzungen von <ref-law> nicht, zumal sich in den Akten keinerlei Hinweise auf Krankheiten finden. Dass bereits ab einem Alter von 40 Jahren der Abschluss bestimmter Zusatzversicherungen nicht mehr problemlos möglich ist, wie dies der Beschwerdeführer letztinstanzlich vorbringt (und mit einem ablehnenden Bescheid einer Krankenkasse betreffend Aufnahme in die Zusatzversicherung belegt), genügt nicht.
5. Nicht gefolgt werden kann dem Beschwerdeführer, soweit er aus der Befreiung von der Versicherungspflicht vom 27. November 2001 Rechte ableiten will. Unbestrittenerweise handelt es sich bei der Befreiung vom Schweizerischen Krankenversicherungsobligatorium um einen Dauersachverhalt, so dass bei Änderung der Rechtslage grundsätzlich eine Anpassung zu erfolgen hat, ausser es fänden sich besondere Übergangsbestimmungen (<ref-ruling> E. 3c S. 393 f.). Dass Übergangsbestimmungen zu <ref-law> fehlen, hat somit entgegen den Vorbringen in der Beschwerde nicht zur Folge, dass eine Anpassung an die geänderte Rechtslage zu unterbleiben hat, sondern bedeutet im Gegenteil, dass eine solche grundsätzlich mit Inkrafttreten des neuen Rechts erfolgen müsste. Weil die Rechtslage seit der Befreiung im Jahre 2001 geändert hat, ist auch die Berufung auf den Vertrauensschutz unbehelflich. Keine Vertrauensgrundlage bildet sodann das blosse Nichthandeln der Zürcher Behörde (hiezu ZBl 2002 S. 582, 1A.19/2001 E. 4b und 2006 S. 439, 1E.13/2004 E. 5.1). Schliesslich macht der Beschwerdeführer nicht geltend, er hätte im Vertrauen auf die bisherige Befreiung nicht wieder gut zu machende Dispositionen getroffen, was Voraussetzung für eine erfolgreiche Berufung auf den Vertrauensschutz wäre.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Schwyz und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 23. April 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle