Sachverhalt:
A. Der 1966 geborene, deutsche Staatsangehörige B._ reiste am 3. Oktober 2005 in die Schweiz ein. Zuerst wohnte er im Kanton Appenzell Ausserrhoden, ab 1. März 2009 in St. Gallen und war bei einer Firma im Fürstentum Liechtenstein angestellt. Nachdem er im Kanton Appenzell Ausserrhoden jeweils von der Obligatorischen Krankenpflegeversicherung befreit worden war, beantragte er dies nach seinem Umzug am 12. Mai 2009 auch bei der Kontrollstelle für Krankenversicherung der Stadt St. Gallen. Mit Verfügung vom 11. Juni 2009 lehnte die Kontrollstelle eine Befreiung vom Versicherungsobligatorium ab; dies bestätigte sie mit Einspracheentscheid vom 10. Juli 2009.
B. Die dagegen erhobene Beschwerde wies das Versicherungsgericht des Kantons St. Gallen mit Entscheid vom 15. März 2010 ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt B._, er sei von der obligatorischen Krankenversicherungspflicht zu befreien.
Das Versicherungsgericht des Kantons St. Gallen beantragt die Gutheissung der Beschwerde, sofern die von B._ eingereichten Bestätigungen der Mannheimer Krankenversicherung AG über seinen Versicherungsschutz in der Schweiz die Voraussetzungen eines gleichwertigen Versicherungsschutzes erfüllten. Die Kontrollstelle für Krankenversicherung schliesst auf Abweisung der Beschwerde. Das vom Bundesgericht zur Vernehmlassung aufgeforderte Bundesamt für Sozialversicherungen (BSV), Geschäftsfeld internationale Angelegenheiten, äussert sich zur Sache, ohne einen ausdrücklichen Antrag zu stellen.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht prüft nach <ref-law> frei, ob der angefochtene Entscheid Bundesrecht verletzt, einschliesslich der von der Schweiz abgeschlossenen internationalen Verträge (<ref-ruling> E. 2; vgl. auch MARKUS SCHOTT, in: Basler Kommentar, Bundesgerichtsgesetz, N. 50 ff. zu <ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>).
2. Streitig und zu prüfen ist, ob Vorinstanz und Verwaltung eine Befreiung des Beschwerdeführers von der obligatorischen Krankenversicherungspflicht zu Recht abgelehnt haben. Nach den Feststellungen der Vorinstanz wohnt der Beschwerdeführer in St. Gallen. Er besitzt als deutscher Staatsangehöriger für die Schweiz eine Aufenthaltsbewilligung B EG/EFTA. Zudem ist er im Fürstentum Liechtenstein erwerbstätig. Angesichts dieses grenzüberschreitenden Sachverhalts stellt sich zunächst die Frage nach dem anwendbaren Recht.
2.1 Am 1. Juni 2002 ist das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.142.112.681) in Kraft getreten. Nach Art. 1 Abs. 1 des auf der Grundlage des Art. 8 FZA ausgearbeiteten und Bestandteil des Abkommens bildenden (Art. 15 FZA) Anhangs II ("Koordinierung der Systeme der sozialen Sicherheit") FZA in Verbindung mit Abschnitt A dieses Anhangs wenden die Vertragsparteien untereinander insbesondere die Verordnung (EWG) Nr. 1408/71 des Rates vom 14. Juni 1971 zur Anwendung der Systeme der sozialen Sicherheit auf Arbeitnehmer und Selbständige sowie deren Familienangehörige, die innerhalb der Gemeinschaft zu- und abwandern (nachfolgend: Verordnung Nr. 1408/71; SR 0.831.109.268.1), und die Verordnung (EWG) Nr. 574/72 des Rates vom 21. März 1972 über die Durchführung der Verordnung (EWG) Nr. 1408/71 über die Anwendung der Systeme der sozialen Sicherheit auf Arbeitnehmer und Selbständige sowie deren Familienangehörige, die innerhalb der Gemeinschaft zu- und abwandern (nachfolgend: Verordnung Nr. 574/72; SR 0.831.109.268.11), oder gleichwertige Vorschriften an.
Titel II der Verordnung Nr. 1408/71 (Art. 13 bis 17a) enthält allgemeine Kollisionsregeln zur Bestimmung der anzuwendenden Rechtsvorschriften. Dabei legt Art. 13 Abs. 1 den kollisionsrechtlichen Grundsatz der Einheitlichkeit der anwendbaren Rechtsvorschriften nach den Regeln gemäss Art. 13 Abs. 2 bis Art. 17a in dem Sinne fest, dass für jede betroffene Person die Rechtsvorschriften nur eines Mitgliedstaates massgebend sind. Ausnahmen vorbehalten, gilt für Arbeitnehmende das Beschäftigungslandprinzip (Grundsatz der lex loci laboris). Dies trifft auch dann zu, wenn sie im Gebiet eines anderen Mitgliedstaates wohnen oder ihr Arbeitgeber oder das Unternehmen, das sie beschäftigt, den Wohn- oder Betriebssitz im Gebiet eines anderen Mitgliedstaates hat (Art. 13 Abs. 2 lit. a der Verordnung Nr. 1408/71).
Im Verhältnis Deutschland - Schweiz, das heisst, bei Erwerbstätigkeit in Deutschland und Wohnsitz in der Schweiz, würde sich deshalb für einen deutschen Staatsangehörigen die Versicherungsunterstellung gemäss Anhang II des FZA und Art. 13 Abs. 2 lit. a und b der Verordnung 1408/71 gemäss dem darin verankerten Beschäftigungslandprinzip in Verbindung mit <ref-law> (vgl. E. 3.1 hernach) nach deutschem Recht richten.
2.2 Im Verhältnis Liechtenstein - Schweiz, das heisst, bei Erwerbstätigkeit in Liechtenstein und Wohnsitz in der Schweiz, wäre (bei einem Staatsangehörigen aus der Schweiz oder Liechtenstein) das als Folge des FZA zwischen der Schweiz und der Europäischen Gemeinschaft sowie ihren Mitgliedstaaten angepasste und in dieser Fassung seit 1. Juni 2002 in Kraft stehende Übereinkommen zwischen Island, Liechtenstein, Norwegen und der Schweiz vom 4. Januar 1960 zur Errichtung der Europäischen Freihandelsassoziation (EFTA-Übereinkommen; SR 0.632.31) massgebend, das zur Koordinierung der Systeme der sozialen Sicherheit (vgl. Art. 21 des Übereinkommens) ebenfalls auf die Verordnung Nr. 1408/71 und die Verordnung Nr. 574/72 verweist (Art. 1 Abs. 1 Anhang K Anlage 2 i.V. m. Abschnitt A dieses Anhangs). Gemäss Ziffer 1.1 Protokoll 2 zu Anlage 2 Anhang K des EFTA-Übereinkommens würde sich im Sinne einer Ausnahme zum Beschäftigungslandprinzip der Verordnung Nr. 1408/71 die Frage der Versicherungsunterstellung in der Krankenpflegeversicherung nach dem Wohnsitzprinzip und damit nach Schweizerischem Recht richten.
2.3 Im Verhältnis Liechtenstein - Deutschland, das heisst, bei Erwerbstätigkeit in Liechtenstein und Wohnsitz in Deutschland, wäre das Abkommen vom 2. Mai 1992 über den Europäischen Wirtschaftsraum, EWR-Abkommen (liechtensteinische Gesetzessammlung Nr. 0.110; siehe auch BBl 1992 IV S. 668 ff.) anwendbar. Gemäss dessen Art. 29 und Anhang VI in Verbindung mit Art. 13 Abs. 2 lit. a der Verordnung Nr. 1408/71 wäre wiederum gemäss Beschäftigungslandprinzip für die Versicherungsunterstellung Liechtensteinisches Recht anwendbar.
2.4 Nun besteht ein dreiseitiges Verhältnis Schweiz/Deutschland/ Liechtenstein; ein deutscher Staatsangehöriger mit Wohnsitz in der Schweiz ist in Liechtenstein erwerbstätig. Die Vorinstanz und das BSV gehen davon aus, dass für solche Konstellationen keine staatsvertragliche Regelung bestehe.
Tatsächlich ist auf die Situation des Beschwerdeführers das FZA nicht anwendbar, da der Beschwerdeführer in Liechtenstein erwerbstätig ist, und die dem Europäischen Wirtschaftsraum (EWR) angeschlossenen EFTA-Staaten Island, Fürstentum Liechtenstein und Norwegen nicht unter den Geltungsbereich des FZA zwischen der Schweiz und der Europäischen Gemeinschaft sowie ihren Mitgliedstaaten fallen. Auch das EFTA-Übereinkommen fällt ausser Betracht, da dieses nur auf Angehörige der Mitgliedstaaten (Island, Fürstentum Liechtenstein, Norwegen und Schweiz) Anwendung findet und damit der Versicherte als deutscher Staatsangehöriger nicht in den persönlichen Anwendungsbereich fällt (8C_994/2009 vom 16. April 2010, E. 6.3.2 [<ref-ruling>]). Schliesslich ist auch das EWR-Abkommen nicht massgeblich, da der Beschwerdeführer in der Schweiz wohnt und die Schweiz dem EWR-Abkommen nicht beigetreten ist.
Nachdem jedoch sowohl im Verhältnis Schweiz - Deutschland (über das FZA), im Verhältnis Schweiz - Liechtenstein (via EFTA-Übereinkommen) als auch im Verhältnis Liechtenstein - Deutschland (via EWR-Abkommen) gleichermassen die massgebende Verordnung Nr. 1408/71 als anwendbar erklärt wird, stellt sich die Frage, ob diese nicht auch im vorliegenden Verhältnis massgeblich sein soll. Allerdings gilt nun im Verhältnis Schweiz - Liechtenstein auf Grund des EFTA-Abkommens gerade eine Ausnahme von der Verordnung Nr. 1408/71, indem hier auf das Wohnortprinzip abgestellt wird (vgl. E. 2.2 hievor). Auf Grund des FZA kann sich der deutsche Staatsangehörige darauf berufen, dass er nicht anders behandelt wird als ein Schweizer in seiner Lage (Art. 2 FZA), d.h. als ein Schweizer mit Wohnsitz in der Schweiz und Erwerbsort in Liechtenstein. Für diesen würde auf Grund des EFTA-Übereinkommens in Bezug auf die Krankenpflegeversicherung das Wohnsitzprinzip gelten. Mit Recht hat die Vorinstanz daher die Streitfrage nach Schweizerischem Recht beurteilt.
3. 3.1 Gemäss <ref-law> muss sich jede Person mit Wohnsitz in der Schweiz innert drei Monaten nach der Wohnsitznahme oder der Geburt in der Schweiz für Krankenpflege versichern oder von ihrem gesetzlichen Vertreter beziehungsweise ihrer gesetzlichen Vertreterin versichern lassen (Abs. 1). Der Bundesrat kann Ausnahmen von der Versicherungspflicht vorsehen, namentlich für Personen, die im Sinne von Artikel 2 Absatz 2 des Gaststaatgesetzes vom 22. Juni 2007 mit Vorrechten, Immunitäten und Erleichterungen begünstigt sind (Abs. 2).
Nach <ref-law> unterstehen der Versicherungspflicht nicht: Personen, die nach dem Freizügigkeitsabkommen sowie seinem Anhang II, dem EFTA-Abkommen, seinem Anhang K und Anlage 2 zu Anhang K oder einem Abkommen über Soziale Sicherheit wegen ihrer Erwerbstätigkeit in einem anderen Staat den Rechtsvorschriften dieses Staates unterstellt sind.
Auf Gesuch hin von der Versicherungspflicht ausgenommen sind gemäss <ref-law> Personen, die nach dem Recht eines Staates, mit dem keine Regelung über die Abgrenzung der Versicherungspflicht besteht, obligatorisch krankenversichert sind, sofern der Einbezug in die schweizerische Versicherung für sie eine Doppelbelastung bedeuten würde und sie für Behandlungen in der Schweiz über einen gleichwertigen Versicherungsschutz verfügen. Dem Gesuch ist eine schriftliche Bestätigung der zuständigen ausländischen Stelle mit allen erforderlichen Angaben beizulegen.
Gemäss <ref-law> sind auf Gesuch hin Personen von der Versicherungspflicht ausgenommen, die über eine Aufenthaltsbewilligung für Personen ohne Erwerbstätigkeit nach dem Freizügigkeitsabkommen oder dem EFTA-Abkommen verfügen, sofern sie während der gesamten Geltungsdauer der Befreiung für Behandlungen in der Schweiz über einen gleichwertigen Versicherungsschutz verfügen. Dem Gesuch ist eine schriftliche Bestätigung der zuständigen ausländischen Stelle mit allen erforderlichen Angaben beizulegen. Die betreffende Person kann die Befreiung oder einen Verzicht auf die Befreiung ohne besonderen Grund nicht widerrufen.
Nach <ref-law> sind auf Gesuch hin Personen von der Versicherungspflicht ausgenommen, 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. Dem Gesuch ist eine schriftliche Bestätigung der zuständigen ausländischen Stelle mit allen erforderlichen Angaben beizulegen. Die betreffende Person kann die Befreiung oder einen Verzicht auf die Befreiung ohne besonderen Grund nicht widerrufen.
3.2 Die Kontrollstelle hat die Befreiung unter dem Titel von Art. 2 Abs. 7 und 8 KVV geprüft, dabei aber offenbar Abs. 7 und Abs. 2 verwechselt (Schreiben vom 11. Juni 2009). Das kantonale Gericht hat die Befreiung unter den Aspekten von Art. 2 Abs. 1 lit. c sowie Abs. 2 und 8 KVV geprüft und ausgeführt, die übrigen Befreiungstatbestände, insbesondere gemäss Abs. 4-7, stünden nicht zur Diskussion.
In seinem Antrag auf Befreiung von der Versicherungspflicht hat sich der Beschwerdeführer nicht auf eine bestimmte Norm berufen, sondern vor allem darauf, dass er bereits in seinem früheren schweizerischen Wohnort (Kanton Appenzell Ausserrhoden) befreit war, wobei auch die damalige Befreiungsverfügung keine gesetzliche Grundlage nennt. In der vorinstanzlichen Beschwerde hat sich der Beschwerdeführer jedenfalls sinngemäss auf den Befreiungstatbestand von <ref-law> berufen, indem er geltend gemacht hat, er verfüge über eine B-Bewilligung, die ihm nicht erlaube, in der Schweiz tätig zu sein. Dass er die massgebende Rechtsnorm nicht genannt hat, schadet ihm nicht, da die Vorinstanz das Recht von Amtes wegen anzuwenden hat (<ref-law>).
Vernehmlassungsweise beantragt nun auch die Vorinstanz Gutheissung gestützt auf <ref-law>. Das BSV ist der Ansicht, diese Bestimmung sei nicht anwendbar. Sie beziehe sich wie Art. 6 FZA und Art. 24 Anhang I FZA auf Personen, die keiner Erwerbstätigkeit nachgehen (Rentner, Personen in Ausbildung), nicht aber auf Personen, die - wie der Beschwerdeführer - im Ausland einer Erwerbstätigkeit nachgehen.
4. 4.1 Nach <ref-law> ausgenommen sind "Personen, die über eine Aufenthaltsbewilligung für Personen ohne Erwerbstätigkeit nach dem Freizügigkeitsabkommen oder dem EFTA-Abkommen" verfügen. Der Ausdruck "ohne Erwerbstätigkeit" bezieht sich grammatikalisch nicht darauf, dass die Person keine Erwerbstätigkeit ausübt, sondern darauf, dass sie eine Aufenthaltsbewilligung besitzt, welche für Personen ohne Erwerbstätigkeit ausgestellt wird. Das geht auch aus dem französischen ("les personnes qui disposent d'une autorisation de séjour pour personnes sans activité lucrative") und italienischen Text ("le persone che dispongono di un permesso di dimora per persone senza attività lucrativa") hervor.
4.2 Die schweizerische Aufenthaltsbewilligung für Personen ohne Erwerbstätigkeit gemäss Art. 10 Abs. 2 AuG kann sich nur darauf beziehen, ob die betreffende Person in der Schweiz eine Erwerbstätigkeit ausübt. Das ergibt sich schon aus allgemeinen völkerrechtlichen Gründen: Ein Staat kann nur Bewilligungen erteilen dafür, ob eine bestimmte Person in seinem Hoheitsgebiet sich aufhalten oder erwerbstätig sein darf. Ob sie allenfalls in einem anderen Staat eine Erwerbstätigkeit ausüben darf, steht ausserhalb der Jurisdiktion und des Einflussbereichs des Aufenthaltsstaates. Dasselbe ergibt sich aus dem systematischen Zusammenhang und dem Sinn und Zweck von <ref-law>: Diese Bestimmung bezieht sich auf die Personen, die ein Aufenthaltsrecht auf Grund von Art. 6 FZA und Art. 24 Anhang I FZA haben. Art. 6 FZA könnte zwar seinem Wortlaut nach so verstanden werden, dass er Personen betrifft, die überhaupt keine Erwerbstätigkeit ausüben. Indessen ist diese Bestimmung im Kontext von Art. 4 und 5 FZA zu sehen, welche das Recht auf Zugang zu einer Erwerbstätigkeit regeln, was sich nur auf die Erwerbstätigkeit im betreffenden Staat beziehen kann (vgl. Art. 1 lit. a und b FZA). Im Gegensatz dazu bezieht sich Art. 6 FZA auf Personen, die im Staat, in dem sie sich aufhalten, keine Erwerbstätigkeit ausüben (Art. 1 lit. c FZA). Klar wird dies sodann aus Art. 24 Anhang I FZA: Diese Bestimmung bezieht sich ausdrücklich auf Personen, die keine Erwerbstätigkeit im Aufenthaltsstaat ausüben. Eine Erwerbstätigkeit in einem anderen Staat schliesst somit die Anwendung von Art. 24 Anhang I FZA nicht aus. In der Regel wird zwar Art. 24 Anhang I FZA auf Personen angewendet, die überhaupt keine Erwerbstätigkeit ausüben (Rentner, Studierende), doch gilt diese Bestimmung nach dem Gesagten auch für Personen, die - wie der Beschwerdeführer - sich in der Schweiz aufhalten, aber nicht hier, sondern in einem anderen Staat eine Erwerbstätigkeit ausüben. Aktenkundig hat denn der Beschwerdeführer genau eine solche Bewilligung, die ihn zwar zum Aufenthalt, aber nicht zur Erwerbstätigkeit in der Schweiz berechtigt. Demzufolge fällt er in den Anwendungsbereich von <ref-law>.
4.3 Damit bleibt als weitere Voraussetzung für die Befreiung des Beschwerdeführers von der Versicherungspflicht gemäss <ref-law> zu prüfen, ob eine zur schweizerischen gleichwertige Versicherungsdeckung besteht (vgl. auch Art. 24 Abs. 1 lit. b Anhang I FZA).
Gleichwertiger Versicherungsschutz besteht, sofern der Versicherte während der ganzen Geltungsdauer der Befreiung über eine gleichwertige Versicherungsdeckung für die Behandlungen in der Schweiz verfügt. Der gleichwertige Versicherungsschutz bezieht sich auf das schweizerische Gesetz. Die ausländische Versicherung muss mindestens die Kosten nach dem Bundesgesetz über die Krankenversicherung (KVG) übernehmen. Es dürfen beispielsweise bei der ausländischen Krankenversicherung keine Limitierungen wie maximale Kosten pro Tag oder maximale Versicherungsdeckung bestehen, da das KVG keine solchen Limitierungen kennt. Zudem müssen sämtliche Leistungen nach KVG auch von der ausländischen Versicherung übernommen werden (vgl. <ref-ruling> E. 5 S. 36 f.).
Diese Voraussetzung ist nach den eingereichten Akten erfüllt. Mit Bescheinigung vom 3. April 2009 bestätigte die Mannheimer Krankenversicherung AG, dass der Beschwerdeführer bei ihr während eines Aufenthaltes in einem anderen Mitgliedstaat der EU und in der Schweiz für Krankheit und Unfall (während der Arbeits- und Freizeit) versichert ist, soweit dafür keine Unfallversicherung aufkommt, und die Versicherung die Kosten der Sachleistungen gemäss den (aufgeführten) KVG-Leistungen deckt.
5. Gerichtskosten werden nicht erhoben (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Versicherungsgerichts des Kantons St. Gallen vom 15. März 2010 und der Einspracheentscheid der Kontrollstelle für Krankenversicherung der Stadt St. Gallen vom 10. Juli 2009 werden aufgehoben. Es wird festgestellt, dass der Beschwerdeführer von der Pflicht zum Abschluss einer schweizerischen Krankenpflegeversicherung befreit ist.
2. Es werden keine Gerichtskosten erhoben.
3. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen, dem Bundesamt für Sozialversicherungen und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 5. November 2010
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Helfenstein Franke