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.

Erwägungen:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Unter Berücksichtigung der Begründungspflicht (Art. 42 Abs. 1 und 2 BGG) prüft es nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind, und ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr aufgegriffen werden (<ref-ruling> E. 1.3 S. 67 f. und 313 E. 2 S. 315, je mit Hinweisen).
2.
Das kantonale Gericht hat in einlässlicher Darstellung der Prämiensituation des Beschwerdeführers im Zeitraum von 2011 bis 2013 erkannt, dass sich die Ausstände per 31. Dezember 2013 auf Fr. 1'004.60 belaufen. Dies wird in der Beschwerde nicht bestritten, weshalb darauf abgestellt werden kann. Auch zu keinen Beanstandungen Anlass gegeben hat letztinstanzlich sodann die - für das Bundesgericht mangels offenkundiger rechtlicher Mängel somit ebenfalls verbindliche - Feststellung der Vorinstanz, wonach die Mahnungen und Betreibungen der Beschwerdegegnerin zu Unrecht erfolgt und dem Beschwerdeführer daher keine Mahn-, Inkasso- und Betreibungskosten aufzuerlegen sind. Streitig und nachfolgend zu prüfen ist, ob der Beschwerdeführer, wie im insoweit angefochtenen Entscheid erwogen, infolge der Ende 2013 noch bestehenden Prämienrestanzen nicht bereits auf diesen, sondern, sobald er den Betrag von Fr. 1'004.60 und allfällige weitere offene Beträge ab dem Jahr 2014 beglichen hat,erst auf den nächstmöglichen Termin aus dem Versicherungsverhältnis mit der Beschwerdegegnerin entlassen werden kann.
3.
Bezahlt die versicherte Person fällige Prämien oder Kostenbeteiligungen nicht, so hat der Versicherer ihr, nach mindestens einer schriftlichen Mahnung, eine Zahlungsaufforderung zuzustellen, ihr eine Nachfrist von 30 Tagen einzuräumen und sie auf die Folgen des Zahlungsverzugs hinzuweisen (<ref-law>). Bezahlt die versicherte Person trotz Zahlungsaufforderung die Prämien, Kostenbeteiligungen und Verzugszinse nicht innert der gesetzten Frist, so muss der Versicherer die Betreibung anheben (<ref-law>). Gemäss <ref-law> kann die säumige versicherte Person den Versicherer nicht wechseln, solange sie die ausstehenden Prämien und Kostenbeteiligungen sowie die Verzugszinse und Betreibungskosten nicht vollständig bezahlt hat. Säumig in diesem Sinne ist die versicherte Person ab Zustellung der Mahnung nach <ref-law> (<ref-law>). Laut <ref-law> muss der Versicherer die Zahlungsaufforderung bei Nichtbezahlung von Prämien und Kostenbeteiligungen spätestens drei Monate ab deren Fälligkeit zustellen. Kündigt eine säumige versicherte Person ihr Versicherungsverhältnis, so muss der Versicherer sie informieren, dass die Kündigung keine Wirkung entfaltet, wenn die bis einen Monat vor Ablauf der Kündigungsfrist gemahnten Prämien, Kostenbeteiligungen und Verzugszinse sowie die bis zu diesem Zeitpunkt aufgelaufenen Betreibungskosten bis zum Ablauf der Kündigungsfrist nicht vollständig bezahlt sind (<ref-law>). Sind die ausstehenden Beträge nach Abs. 2 beim Versicherer nicht rechtzeitig eingetroffen, so muss dieser die betroffene Person informieren, dass sie weiterhin bei ihm versichert ist und frühestens auf den nächstmöglichen Termin nach Art. 7 Abs. 1 und 2 KVG den Versicherer wechseln kann. Der Versicherer muss zudem den neuen Versicherer innerhalb von 60 Tagen darüber informieren, dass die versicherte Person weiterhin bei ihm versichert ist (<ref-law>).
4.
4.1. Unbestrittenermassen bestanden Ende Dezember 2013 noch Prämienausstände des Beschwerdeführers in der Höhe von Fr. 1'004.60. Dieses Tatbestandselement des <ref-law> mit der Rechtsfolge des Ausschlusses des Versichererwechsels ist demnach - mit der Vorinstanz - zu bejahen.
4.2. Nicht Rechnung getragen hat das kantonale Gericht jedoch dem Umstand, dass das gesetzlich verankerte Austrittsverbot gemäss Wortlaut der Gesetzesbestimmung nur die mit Blick auf Prämien und Kostenbeteiligungen "säumige" versicherte Person treffen kann. Säumigkeit in diesem Sinne liegt laut den hievor zitierten Verordnungsnormen ab Zustellung der Mahnung nach <ref-law> vor. Da nach den - verbindlichen (vgl. E. 2 hievor) - Vorgaben des kantonalen Gerichts von mit Bezug auf die Prämienausstände verfrühten und damit rechtsunwirksamen Mahnungen sowie zu Unrecht angehobenen Betreibungen auszugehen ist, hat der Beschwerdeführer nicht als "säumig" gemäss <ref-law> in Verbindung mit <ref-law> zu gelten. Nur unter dieser Voraussetzung entfaltet indessen die von ihm am 20. Juni 2013 ausgesprochene Kündigung keine Rechtswirkung (vgl. auch Gebhard Eugster, Die obligatorische Krankenpflegeversicherung, in: Soziale Sicherheit, SBVR Bd. XIV, 3. Aufl. 2016, S. 457 Rz. 167). Die in <ref-law> vorgesehene Sanktionsfolge kann daher nicht eintreten und der Beschwerdeführer, der nach eigener Aussage seit 1. Januar 2014 obligatorisch bei der Concordia Schweizerische Kranken- und Unfallversicherung AG krankenversichert ist, muss per Ende 2013 aus dem Versicherungsverhältnis mit der Beschwerdegegnerin entlassen werden. Er hat somit zwar noch die für die Jahre 2011 bis 2013 ausgewiesenen Prämienausstände zu begleichen, eine weitergehende die Beschwerdegegnerin betreffende vertragliche Verpflichtung besteht aber nicht. Ein durch die Verunmöglichung des Versichererwechsels entstandener Schaden, welchen die Beschwerdegegnerin gemäss <ref-law> zu ersetzen hätte (vgl. Eugster, a.a.O., S. 457 Rz. 167), wird nicht geltend gemacht, sodass darauf an dieser Stelle nicht näher einzugehen ist.
5.
Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten der Beschwerdegegnerin zu überbinden (<ref-law>). Sie hat dem anwaltlich vertretenen Beschwerdeführer ferner eine angemessene Parteientschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Dispositiv-Ziffer 2 Absatz 2 des Entscheids des Kantonsgerichts Appenzell Innerrhoden vom 21. Mai 2015 wird insoweit abgeändert, als der Beschwerdeführer auf den 31. Dezember 2013 aus dem mit der Beschwerdegegnerin begründeten obligatorischen Krankenpflegeversicherungsverhältnis zu entlassen ist.
2.
Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4.
Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Kantonsgericht Appenzell Innerrhoden zurückgewiesen.
5.
Dieses Urteil wird den Parteien, dem Kantonsgericht Appenzell Innerrhoden und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 7. Juli 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Die Gerichtsschreiberin: Fleischanderl