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.