Sachverhalt: A. A.a. A._ war seit 1. Januar 2008 obligatorisch bei der Philos Krankenversicherung AG (nachfolgend: Philos) krankenpflegeversichert. Am 8. September 2011 gab er der Philos telefonisch bekannt, dass er seit dem 1. August 2011 nicht mehr in Appenzell, sondern im Kanton St. Gallen wohne. In der Folge erfasste die Philos die Adressänderung per 1. September 2011, unterliess es aber in der Folge, die Tarifanpassung auf St. Gallen vorzunehmen. Am 18. März 2013 informierte A._ die Krankenversicherung darüber, dass er ab 1. April 2013 wieder in Appenzell wohnhaft sein werde. Am 10. Juni 2013 stellte die Philos ihm diverse Rechnungen betreffend Prämienausstände aus den Jahren 2011 bis 2013, zahlbar bis 31. Juli 2013, zu. Mit Schreiben vom 20. Juni 2013 kündigte A._ das Versicherungsverhältnis für sich und seinen Sohn auf 31. Dezember 2013. Am 24. Juni 2013 sandte die Philos ihm zwei weitere berichtigte Rechnungen betreffend Prämien des Jahres 2013 zu, woraufhin A._ am 2. Juli 2013 für die Prämien Juni, Juli und August 2013 den Betrag von Fr. 1'289.70 überwies. Am 3. Juli 2013 bestätigte die Philos den Erhalt der Kündigung und gab dem Versicherten die Kündigungsbedingungen bekannt; insbesondere wurde er darauf hingewiesen, dass ein Versicherungswechsel nur möglich sei, wenn keine Zahlungsausstände mehr bestünden. Mit Aufstellungen vom 11. und 15. Juli 2013 listete der Krankenversicherer die noch offenen Prämienbeträge 2011 bis 2013 auf. Am 18. August sowie 19. und 21. Oktober 2013 mahnte die Philos den Versicherten für am 10. und 24. Juni 2013 in Rechnung gestellte und noch nicht beglichene Prämien und erhob Mahnspesen. Mit Schreiben vom 4. und 29. Oktober 2013 ersuchte der Rechtsvertreter von A._ um Erläuterung des Prämienverlaufs, der zusätzlichen Rechnungen, der zahlreichen Rechnungsberichtigungen und der sich darauf beziehenden Mahnungen. Nachdem die Philos am 5. November 2013 eine Kontoübersicht zugestellt hatte, wies der Rechtsvertreter des Versicherten mit Eingaben vom 19. und 29. November 2013 darauf hin, dass die Abrechnung die notwendige Klarheit vermissen lasse. Am 31. Januar 2014 teilte der Krankenversicherer mit, dass die am 20. Juni 2013 ausgesprochene Kündigung nicht akzeptiert werden könne, da noch Prämienrestanzen vorhanden seien. Dagegen opponierte A._ mit Schreiben vom 7. Februar 2014. Nach weiterer Korrespondenz stellte die Philos am 10. Juni 2014 Betreibungsbegehren hinsichtlich am 10. Juni 2013 für die Jahre 2011 und 2012 geforderter Prämien. Gegen die Zahlungsbefehle vom 17. Juni 2014 erhob A._ gleichentags Rechtsvorschläge. Diese beseitigte der Krankenversicherer am 14. Juli 2014 verfügungsweise, bestätigt mit Einspracheentscheiden vom 10. November 2014. A.b. Mit Verfügung vom 18. Juni 2014 bekräftigte die Philos Prämienausstände für den Zeitraum von 2011 bis 2013 in der Höhe von insgesamt Fr. 1'190.90 einschliesslich Spesen. Daran wurde auf Einsprache hin mit der Begründung festgehalten, dass per 31. Dezember 2013 Prämienrestanzen inklusive Verwaltungskosten (Mahnung, Aufforderung, Aktenöffnung) und Betreibungsspesen im Umfang von Fr. 1'440.40 offen seien; der Versicherte könne daher nicht aus dem Versicherungsvertrag entlassen werden (Einspracheentscheid vom 9. Dezember 2014). B. Die gegen den Einspracheentscheid der Philos vom 9. Dezember 2014 eingereichte Beschwerde hiess das Kantonsgericht Appenzell Innerrhoden mit Entscheid vom 21. Mai 2015 teilweise gut und hob die Verfügung der Philos vom 18. Juni 2014 und deren Einspracheentscheid vom 9. Dezember 2014 auf. Es kam dabei zum Schluss, dass A._ der Philos per 31. Dezember 2013 noch Prämien für die Jahre 2011 bis 2013 im Gesamtbetrag von Fr. 1'004.60 schulde. Die in Zusammenhang mit den Ausständen ergangenen Mahnungen und Betreibungen seien indessen, da der Versicherte diverse Male erfolglos versucht habe, Erklärungen für die Rechnungsstellungen und bezüglich der genauen Zusammensetzung des geforderten Betrags zu erhalten, seitens der Philos verfrüht und daher zu Unrecht erfolgt, weshalb die damit verbundenen Kosten nicht dem Versicherten auferlegt werden könnten. Auf Grund der Ende 2013 noch bestehenden Restanzen sei dieser aber erst auf den nächstmöglichen Termin aus dem Versicherungsverhältnis zu entlassen, sofern er bis dahin sämtliche Kosten beglichen habe. C. A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, in Aufhebung des angefochtenen Entscheids sei festzustellen, dass er bei Zahlung des Betrages von Fr. 1'004.60 auf den 31. Dezember 2013 aus dem obligatorischen Krankenpflegeversicherungsverhältnis mit der Philos zu entlassen sei. Die Philos beantragt die Abweisung der Beschwerde. Das Bundesamt für Gesundheit verzichtet auf eine Stellungnahme.