Sachverhalt:
A. A.a Der in X._ wohnhafte K._ ist bei der Concordia Krankenversicherung (nachfolgend: Concordia) obligatorisch krankenpflegeversichert. Auf Betreibungsbegehren der Concordia hin stellte das Betreibungsamt X._ am 27. Februar 2002 bezüglich ausstehender Versicherungsprämien für die Monate März bis Dezember 2001 einen Zahlungsbefehl (Nr. 45937) und auf Fortsetzungsbegehren hin am 23. April 2003 eine entsprechende Pfändungsurkunde und einen Verlustschein gemäss <ref-law> aus. In der Folge ersuchte die Concordia das Sozialamt der (damals zuständigen) Gemeinde Y._ am 28. April 2003 um Übernahme der Prämienausstände von März bis Dezember 2001 (10 x Fr. 200.80) sowie der angefallenen Betreibungskosten und teilte mit, bis die ausstehenden Forderungen vollständig bezahlt seien, werde die Übernahme der Kosten für Leistungen gestützt auf den seit 1. Januar 2003 in Kraft stehenden Art. 90 Abs. 4 der Verordnung über die Krankenversicherung (KVV) aufgeschoben. Die Einwohnergemeinde Y._ vergütete daraufhin lediglich die Prämienausstände, nicht aber die Betreibungskosten, was die Concordia zur Fortsetzung des Leistungsaufschubs veranlasste.
A.b Am 9. August 2005 ersuchten die (neu zuständigen) Sozialen Dienste der Stadt X._ die Concordia um Aufhebung des Leistungsaufschubs unter Hinweis darauf, für vor dem 1. Januar 2003 angefallene Prämienausstände habe die Sozialbehörde gemäss Anweisung des Kantons Solothurn keine Betreibungskosten zu übernehmen. Mit Schreiben vom 17. August 2005 bestritt die Concordia dies unter Berufung auf die seit 1. Januar 2003 geltende Rechtslage, welche hier anwendbar sei und einen Leistungsaufschub auch bei nicht vollständiger Bezahlung von Betreibungskosten erlaube. Die Sozialen Dienste verlangten daraufhin von der Concordia erfolglos den Erlass einer beschwerdefähigen Verfügung.
B. Die dagegen erhobene Beschwerde der Concordia nahm das Versicherungsgericht des Kantons Solothurn als Rechtsverweigerungsbeschwerde entgegen; es hiess diese, soweit es darauf eintrat, gut und wies die Concordia Krankenversicherung an, im Sinne der Erwägungen eine beschwerdefähige Verfügung zu erlassen (Entscheid vom 31. Januar 2006).
C. Mit Verwaltungsgerichtsbeschwerde beantragt die Concordia die Aufhebung des vorinstanzlichen Entscheids.
Die Stadt X._ schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde. Das Bundesamt für Gesundheit verzichtet vernehmlassungsweise auf einen förmlichen Antrag, hält jedoch dafür, dass der angefochtene Entscheid im Ergebnis richtig sei.

Das Bundesgericht zieht in Erwägung:
1. Am 1. Januar 2007 ist das Bundesgesetz über das Bundesgericht vom 17. Juni 2005 (BGG; SR 173.110) in Kraft getreten (AS 2006 1205, 1243). Da der angefochtene Entscheid vorher ergangen ist, richtet sich das Verfahren noch nach OG (<ref-law>; <ref-ruling> Erw. 1.2).
2. Materiell-rechtlicher Ausgangspunkt der Streitigkeit bildet die Frage, ob die Beschwerdeführerin den gegenüber K._ verhängten Leistungsaufschub gestützt auf <ref-law> in der seit 1. Januar 2003 bis 31. Dezember 2005 gültig gewesenen Fassung (ab 1. Januar 2006 vgl. <ref-law>) fortzusetzen befugt ist, bis die Sozialen Dienste der Stadt X._ die Betreibungskosten beglichen haben, welche im Zusammenhang mit der fruchtlosen, durch Verlustschein dokumentierten Betreibung von - inzwischen beglichenen - Prämienforderungen gegenüber K._ für die Monate März bis Dezember 2001 entstanden sind. In dieser KVG-rechtlichen Streitigkeit hat sich die Concordia entgegen dem ausdrücklichen Begehren der Sozialen Dienste der Stadt X._ bisher geweigert, eine beschwerdefähige Verfügung zu erlassen. Gegenstand des Verfahrens ist die prozessuale Frage, ob die Vorinstanz zu Recht auf die von der Stadt X._ - ohne Bevollmächtigung durch den Versicherten - gegen das Untätigbleiben des Krankenversicherers erhobene Rechtsverweigerungsbeschwerde eingetreten ist und die Beschwerdeführerin verpflichtet hat, gegenüber den Sozialen Diensten der Stadt X._ in der Streitsache eine anfechtbare Verfügung zu erlassen.
3. 3.1 Gemäss <ref-law> hat der Versicherungsträger über Leistungen, Forderungen und Anordnungen, die erheblich sind oder mit denen die betroffene Person nicht einverstanden ist, schriftlich Verfügungen zu erlassen. Erlässt er eine Verfügung, welche die Leistungspflicht eines andern Versicherungsträgers berührt, so hat er auch ihm die Verfügung zu eröffnen, und dieser kann die gleichen Rechtsmittel ergreifen wie die versicherte Person (<ref-law>).
3.2 Leistungen, Forderungen und Anordnungen, die nicht unter <ref-law> fallen, können in einem formlosen Verfahren behandelt werden (<ref-law>), doch kann die betroffene Person den Erlass einer Verfügung verlangen (<ref-law>). Erlässt der Versicherungsträger entgegen dem Begehren der betroffenen Person keine Verfügung oder keinen Einspracheentscheid (vgl. 52 ATSG), steht dieser gemäss <ref-law> dagegen die Beschwerde an das kantonale Versicherungsgericht (<ref-law>) offen, sofern sie die Legitimationsvoraussetzungen im Sinne von <ref-law> erfüllt. Das Beschwerderecht gemäss <ref-law> dient der Durchsetzung des auf Verfassungsstufe als Teilgehalt von <ref-law> anerkannten Verbots der formellen Rechtsverweigerung, die eine Behörde namentlich dann begeht, wenn sie pflichtwidrig völlig untätig bleibt (<ref-ruling> Erw. 6b = Pra 78/1989 Nr. 9 S. 48 Erw. 6b; Urteil 1A.63/2005 der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 22. August 2005, Erw. 3.1; Jörg Paul Müller, Grundrechte in der Schweiz, 3. Auflage, Bern 1999, S. 497 f.).
3.3 In der Krankenversicherung werden gemäss <ref-law> auch erhebliche Leistungen grundsätzlich im formlosen Verfahren nach <ref-law> gewährt (<ref-law>). Die Bestimmung tangiert indessen weder die in <ref-law> verankerte Verpflichtung des Versicherungsträgers, bei fehlendem Einverständnis der betroffenen Person schriftlich zu verfügen (vgl. Erw. 3.1 hievor), noch deren Befugnis, gestützt auf <ref-law> den Erlass einer Verfügung zu verlangen und vom Beschwerderecht nach Massgabe von Art. 56 Abs. 2 in Verbindung mit <ref-law> (vgl. Erw. 3.2 hievor) Gebrauch zu machen.
4. 4.1 Die Parteien sind sich einig, dass sich die umstrittene Legitimation der Stadt X._, in eigenem Namen Rechtsverweigerungsbeschwerde (<ref-law>; vgl. Erw. 3.2 hievor) zu erheben, nach <ref-law> richtet. Gemäss dem - auf das Beschwerderecht nach <ref-law> zugeschnittenen - Wortlaut dieser Bestimmung ist zur Beschwerde berechtigt, wer durch die angefochtene Verfügung berührt ist und ein schutzwürdiges Interesse an deren Aufhebung oder Änderung hat. Bezogen auf die Rechtsverweigerungsbeschwerde bedeutet dies, dass zu deren Erhebung legitimiert ist, wer durch das Fehlen einer anfechtbaren Verfügung berührt ist und ein schutzwürdiges Interesse an deren Erlass hat. Die Begriffe des "Berührtseins" und des "schutzwürdigen Interesses" gemäss <ref-law> sind dabei praxisgemäss in gleicher Weise auszulegen wie für das bundesrechtliche Verwaltungsgerichtsbeschwerdeverfahren gemäss Art. 103 lit. a OG (<ref-ruling> Erw. 3.1 mit Hinweisen; vgl. Erw. 4.3 hernach).
4.2 Entgegen dem in der Verwaltungsgerichtsbeschwerde vertretenen Standpunkt verlaufen die Beschwerdelegitimation gemäss <ref-law> und Art. 103 lit. a OG (sowie gleichlautendem <ref-law>) und die Berechtigung, den Erlass einer anfechtbaren Verfügung zu verlangen, mit Blick auf die Einheit des Prozesses grundsätzlich parallel: Dies ergibt sich aus dem Parteibegriff gemäss <ref-law> und - für das Sozialversicherungsverfahren - gemäss <ref-law>. Danach kommt nebst Verfügungsadressaten allen Personen, Organisationen oder Behörden Parteistellung zu, denen ein Rechtsmittel gegen die Verfügung - im Sozialversicherungsverfahren: eines Versicherungsträgers oder eines ihm gleichgestellten Durchführungsorgans - zusteht. Die Vorschriften über die Beschwerdelegitimation sind demnach massgebend für die Parteistellung (auch bereits) im erstinstanzlichen Verwaltungsverfahren (vgl. etwa <ref-ruling> Erw. 3b/bb, 124 V 397 Erw. 2a, 123 II 378 Erw. 2; Pra 2001 Nr. 190 S. 1155, Erw. 1a [Urteil 2A.96/2000 der II. öffentlich-rechtlichen Abteilung des Bundesgerichts vom 25. Juli 2001]; Urteil 1A.253/2005 der I. öffentlich-rechtlichen Abteilung des Bundesgerichts vom 17. Februar 2006, Erw. 2.1.1) und somit gegebenenfalls für den Anspruch auf Erlass einer Verfügung als Voraussetzung dafür, die Parteistellung überhaupt wirksam geltend machen zu können (vgl. <ref-ruling> f. Erw. 4.3.3); dies gilt nicht nur für Feststellungsverfügungen im Sinne von <ref-law> (siehe etwa <ref-ruling> ff.), sondern auch für Leistungs- oder Gestaltungsverfügungen (so ausdrücklich Pra 1998 Nr. 70 S. 438, Erw. 2b [Urteil 2A.185/1997 der II. öffentlich-rechtlichen Abteilung des Bundesgerichts vom 11. Februar 1998], Erw. 2b mit Hinweisen auf Rechtsprechung und Lehre).
4.3 4.3.1 Nach der zu Art. 103. lit. a OG ergangenen, auch für die Auslegung von <ref-law> massgebenden Rechtsprechung (vgl. Erw. 4.1 hievor in fine) gilt als schutzwürdiges Interesse im legitimationsrechtlichen Sinne jedes praktische oder rechtliche Interesse, welches eine von einer Verfügung betroffene Person an deren Änderung oder Aufhebung geltend machen kann. Das schutzwürdige Interesse besteht somit im praktischen Nutzen, den die Gutheissung der Beschwerde dem Verfügungsadressaten verschaffen würde, oder - anders ausgedrückt - im Umstand, einen Nachteil wirtschaftlicher, ideeller, materieller oder anderweitiger Natur zu vermeiden, welchen die angefochtene Verfügung mit sich bringen würde. Das rechtliche oder auch bloss tatsächliche Interesse braucht somit mit dem Interesse, das durch die von der beschwerdeführenden Person als verletzt bezeichnete Norm geschützt wird, nicht übereinzustimmen. Immerhin wird verlangt, dass die Person durch die angefochtene Verfügung stärker als jedermann betroffen sei und in einer besonderen, beachtenswerten, nahen Beziehung zur Streitsache stehe (<ref-ruling> Erw. 1.2, 588 Erw. 2.1, 651 Erw. 3.1, 131 V 300 Erw. 3, 130 V 202 Erw. 3, 515 Erw. 3.1, 563 Erw. 3.3, 127 V 3 Erw. 1b, 82 Erw. 3a/aa).
Das in Art. 103 lit. a OG, <ref-law> und <ref-law> zusätzlich erwähnte "Berührtsein" stellt nicht eine selbstständige und damit kumulativ zum schutzwürdigen Interesse zu erfüllende Legitimationsvoraussetzung, sondern letztlich eine Präzisierung desselben dar (vgl. Urteil S. vom 7. September 2004 [I 215/03] Erw. 2.2; in diesem Sinne auch Fritz Gygi, Bundesverwaltungsrechtspflege, 2., überarbeitete Auflage, Bern 1983, S. 156; Alfred Kölz/Isabelle Häner, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2. Auflage, Zürich 1998, S. 193, Rz. 536; Ulrich Zimmerli/Walter Kälin/ Regina Kiener, Grundlagen des öffentlichen Verfahrensrechts, Bern 2004, S. 102; Ueli Kieser, ATSG-Kommentar, Zürich/Basel/Genf 2003, zu Art. 59, Rz. 4). Ob es sich unter dem ab 1. Januar 2007 in Kraft stehenden BGG noch so verhält, ist damit nicht präjudiziert.
4.3.2 Die Beschwerdelegitimation gemäss Art. 103 lit. a OG (und <ref-law>) ist in erster Linie auf Privatpersonen zugeschnitten. Nach der Rechtsprechung schliesst dies indessen nicht aus, dass sich auch eine Behörde zur Begründung ihrer Beschwerdebefugnis auf diese Bestimmung berufen kann, sofern sie mit der Beschwerdeführung nicht nur ein öffentliches Interesse an der richtigen Durchführung des Bundesrechts, sondern wie ein Privater ein bestimmtes, eigenes finanzielles Interesse verfolgt (<ref-ruling> Erw. 2, 113 Ib 32 Erw. 2; AHI 1995 S. 95 Erw. 3a) oder aber in schutzwürdigen eigenen hoheitlichen Interessen berührt ist (<ref-ruling> Erw. 4.3.1, mit Hinweisen).
4.3.3 Besondere Bedeutung kommt dem Legitimationserfordernis zu, wenn nicht der Verfügungsadressat im materiellen Sinn, sondern ein Dritter (Drittbeschwerdeführer) den Entscheid anficht (<ref-ruling> Erw. 3a/aa mit Hinweisen). Hier haben die Legitimationsanforderungen die Funktion, die Popularbeschwerde auszuschliessen, weshalb bei der Bejahung der Beschwerdelegitimation von Drittbeschwerdeführern Zurückhaltung geboten ist. Erforderlich ist ein spezifisches Rechtsschutzinteresse, welches nur bejaht wird, wenn der Dritte ein unmittelbares und konkretes Interesse an der Aufhebung oder Änderung der Verfügung (<ref-ruling> Erw. 3b; AHI 1995 S. 95 Erw. 3a in fine) - hier: am Erlass einer Verfügung - hat oder eine spezifische, besonders nahe Beziehung zur Streitsache für sich in Anspruch nehmen kann. Das allgemeine Interesse an der richtigen Auslegung und Durchsetzung des Bundesrechts genügt nicht (<ref-ruling> Erw. 3a/bb; zum Ganzen statt vieler: ARV 2005 S. 147 f. Erw. 1.4 und 1.5 mit Hinweisen [Urteil F. vom 14. Oktober 2004, C 12/04]).
4.4 Unter dem Blickwinkel der unter Erw. 4.3 dargelegten Rechtsprechung hat das Eidgenössische Versicherungsgericht die Legitimation von Sozialhilfebehörden zur Erhebung einer Drittbeschwerde konkret unterschiedlich beurteilt.
4.4.1 Im Urteil K. vom 8. Juni 2005 [I 113/05] erachtete das Gericht die Sozialhilfebehörde, die einen Versicherten regelmässig (in casu: seit fünf Jahren) unterstützt, als legitimiert, die den Rentenanspruch ablehnende Verfügung der IV-Stelle in eigenem Namen mit Einsprache anzufechten und gegen den Einspracheentscheid Beschwerde zu führen. In einem weiteren Fall entschied es, dass das Sozialamt, welches Unterhaltsbeiträge zu Gunsten des Kindes eines EL-Bezügers bevorschusst, aufgrund besonderer Betroffenheit legitimiert ist, gegen eine EL-Verfügung, welche die Alimentenbevorschussung bei der Berechnung des EL-rechtlich anrechenbaren Einkommens berücksichtigt, (Dritt-)Beschwerde zu erheben (SVR 2005 EL Nr. 7 S. 15 [Urteil I. vom 26. November 2004, P 37/04]). Im Urteil O. vom 31. Januar 2003 [P 27/01] leitete das Gericht die Beschwerdelegitimation einer Sozialhilfebehörde zur Anfechtung der einen von ihr unterstützten Versicherten betreffenden Verfügung über Ergänzungsleistungen aus der gesetzlich verankerten Befugnis der Sozialbehörde ab, aus eigenem Recht den EL-Anspruch im Anmeldeverfahren geltend zu machen (Art. 20 Abs. 1 ELV in Verbindung mit <ref-law> [in der bis 31. Dezember 2002 gültig gewesenen Fassung]).
4.4.2 Verneint hat das Eidgenössische Versicherungsgericht die Beschwerdelegitimation der einen Arbeitslosen unterstützenden Sozialhilfebehörde, welche beim kantonalen Versicherungsgericht eine dem Unterstützten eröffnete Verfügung der Arbeitslosenkasse betreffend Anrechnung einer Tätigkeit als Zwischenverdienst angefochten hatte. Das Gericht erwog, einerseits fehle es an einer spezialgesetzlichen oder aus dem ATSG ableitbaren Befugnis der unterstützenden Fürsorgebehörde, aus eigenem Recht ALV-rechtliche Leistungen im Anmeldeverfahren geltend zu machen; die Konnexität zwischen einer solchen Befugnis und der Beschwerdelegitimation sei hier mithin - anders als in den Bereichen AHV, IV und EL - nicht gegeben. Andererseits sei angesichts der im Falle von Drittbeschwerden erhöhten Anforderungen an das Rechtsschutzinteresse das unmittelbare und konkrete Interesse der Sozialbehörde zu verneinen (ARV 2005 S. 150 ff. Erw. 4 und 5 [Urteil F. vom 14. Oktober 2004, C 12/04], mit Rechtsprechungsübersicht). Mangels eines unmittelbaren und konkreten Interesses ist die Sozialhilfebehörde gemäss einem weiteren Urteil auch nicht legitimiert, gegen eine die Vermittlungsfähigkeit eines von ihr unterstützten Asylbewerbers verneinende Verfügung der Arbeitslosenkasse Beschwerde zu erheben (ARV 1999 Nr. 14 S. 78 ff. Erw. 2). An der Legitimation zur Drittbeschwerde fehlt es der Sozialhilfebehörde schliesslich auch bezüglich einer nach dem Tod des von ihr unterstützten Versicherten erlassenen Rentenverfügung; das finanzielle Interesse der Behörde allein bedeutet nicht, dass diese unmittelbar und stärker als jedermann betroffen ist oder in einer besonderen, beachtenswerten, nahen Beziehung zur Streitsache steht (AHI 1995 S. 95 f. Erw. 3b).
4.5 Die Sozialhilfebehörden sind somit nicht allein aufgrund des Umstands, dass sie einen Versicherten unterstützen, generell zur Anfechtung leistungsablehnender Verfügungen der Sozialversicherungsträger berechtigt, auch wenn in allen diesen Fällen ein mittelbares finanzielles Interesse daran besteht, dass der Lebensunterhalt durch die Sozialversicherung und nicht durch die - subsidiäre - öffentliche Sozialhilfe sichergestellt ist (vgl. auch <ref-ruling> Erw. 5b; Urteil 1A.260/2000 der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 27. Februar 2001, Erw. 2c). Die Legitimation zur Drittbeschwerde verlangt vielmehr auch hier eine unmittelbare und konkrete Betroffenheit oder qualifizierte Beziehungsnähe zur Streitsache (vgl. Erw. 4.3.3 hievor).
5. Entgegen der Auffassung der Beschwerdeführerin ist das vorangehend umschriebene Legitimationserfordernis im hier zu beurteilenden Sachzusammenhang erfüllt. Zu bejahen ist es nicht aufgrund des (bloss mittelbaren) finanziellen Interesses der Beschwerdegegnerin, das sich aus der allgemeinen sozialhilferechtlichen Unterstützungspflicht ergibt, welche die Stadt X._ nach kantonalem Recht gegenüber K._ trifft, sondern aus den spezifischen bundesrechtlichen Vorschriften über die Prämienerhebung und die Folgen des Zahlungsverzugs, wie sie seit 1. Januar 2003 in <ref-law> verankert sind und zuvor in <ref-law> geregelt waren (zur Auslegung dieser Bestimmungen: <ref-ruling>) und welche das Verhältnis Versicherer - Sozialhilfebehörde ausdrücklich normieren: Die Befugnis des Krankenversicherers, die Leistungen bis zur vollständigen Bezahlung der ausstehenden Prämien und Kostenbeteiligungen (so altArt. 9 Abs. 2 KVV) sowie ab 1. Januar 2003 (auch) der hier umstrittenen Betreibungskosten aufzuschieben (<ref-law> in der vom 1. Januar 2003 bis 31. Dezember 2005 gültig gewesenen Fassung) bzw. die Forderungen mit Leistungen zu verrechnen (vgl. nunmehr ab 1. Januar 2006 <ref-law>; <ref-law>), ist gebunden an die vorgängig erfolgte Meldung an die Sozialhilfebehörde (Art. 90 Abs. 3 und 4 KVV in der Fassung vom 1. Januar 2003 bis 31. Dezember 2005) bzw. an die zuständige kantonale Stelle, welche die Kosten allenfalls übernimmt (<ref-law> in der ab 1. Januar 2006 geltenden Fassung). In der Praxis führt dies dazu, dass die Krankenversicherer die entsprechenden Leistungen direkt bei der zuständigen Sozialhilfebehörde einfordern, um den Aufschub der Leistungen zu vermeiden; so ist die Beschwerdeführerin auch im vorliegenden Fall vorgegangen (vgl. Schreiben der Beschwerdeführerin vom 28. April 2003, 19. Juli 2005 und 17. August 2005 an die zuständigen Sozialämter]). Die Sozialhilfebehörde hat dadurch eine besondere Stellung, welche sich von anderen Fällen unterscheidet, in denen eine Sozialversicherungsleistung verweigert wird, was bloss mittelbar zu einer Leistungspflicht der Sozialhilfe führen kann.
Bei dieser Sach- und Rechtslage hat die Stadt X._ als das die unterstützende Sozialhilfebehörde tragende Gemeinwesen ein schützenswertes Interesse an einem förmlichen Entscheid über die unter Erw. 2 dargelegte Rechtsfrage. Die Beschwerdelegitimation im Sinne von <ref-law> in Verbindung mit <ref-law> und damit auch der Anspruch auf eine beschwerdefähige Verfügung gemäss Art. 51 Abs. 2 in Verbindung mit <ref-law> (vgl. Erw. 3.2 hievor) ist daher zu bejahen und der vorinstanzliche Entscheid im Ergebnis zu bestätigen.
6. Das Verfahren ist kostenpflichtig, da es nicht um die Bewilligung oder Verweigerung von Versicherungsleistungen geht (Art. 134 OG [vgl. Erw. 1 hievor] e contrario).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 1000.- werden der Beschwerdeführerin auferlegt.
3. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Solothurn und dem Bundesamt für Gesundheit zugestellt.
Luzern, 8. Januar 2007
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: