Sachverhalt:
A. A.a Der Kanton Zürich, die Ärztegesellschaft des Kantons Zürich (AGZ) und die Helsana Versicherungen AG (nachfolgend: Helsana) schlossen am 8./9. Februar 2001 einen Rahmenvertrag über die obligatorische Krankenpflegeversicherung für Asylsuchende, vorläufig Aufgenommene und Schutzbedürftige ohne Aufenthaltsbewilligung, die von den zuständigen Fürsorgebehörden ganz oder teilweise unterstützt werden (nachfolgend: Rahmenvertrag). Dieser sieht eine eingeschränkte Wahl des Leistungserbringers sowie die Kostenvergütung nach dem System des tiers payant vor. Die zur Auswahl stehenden Leistungserbringer werden von den Vertragsparteien gemeinsam aus einer durch die AGZ erstellten Liste bestimmt. Diese sog. Asyl-Hausarztliste wurde auf den 1. Juli 2001 definitiv eingeführt.
Der nicht auf der Liste stehende Dr. med. M._ behandelte in der Zeit vom 25. Juli bis 15. August 2001 den vom 1. April bis 31. August 2001 mittels Rahmenvertrag versicherten Asylbewerber K._. Als er von der Helsana mit Rechnung vom 4. Oktober 2001 die Vergütung der erbrachten Leistungen forderte, lehnte die Helsana die Kostenübernahme ab. Daraufhin trat K._ allfällige Ansprüche gegenüber der Helsana an Dr. med. M._ ab.
A.b Nachdem Dr. med. M._ beim Schiedsgericht in Sozialversicherungsstreitigkeiten des Kantons Zürich Klage auf Bezahlung der Rechnung erhoben und letztinstanzlich das damalige Eidgenössische Versicherungsgericht (seit 1. Januar 2007: Bundesgericht) die Zuständigkeit des Schiedsgerichts verneint hatte (Urteil K 66/02 vom 17. August 2004, publiziert in RKUV 2005 Nr. KV 312 S. 3), lehnte die Helsana mit Verfügung vom 8. November 2004 und Einspracheentscheid vom 8. Februar 2005 die Kostenübernahme ab.
B. Die von Dr. med. M._ dagegen erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 30. November 2006 gut. Es verpflichtete die Helsana, Dr. med. M._ die Kosten der Behandlung von K._ zu erstatten.
C. Die Helsana erhebt Verwaltungsgerichtsbeschwerde mit dem Antrag, der kantonale Entscheid sei aufzuheben.
Dr. med. M._ schliesst auf Abweisung der Beschwerde, während das Bundesamt für Gesundheit auf eine Vernehmlassung verzichtet.

Das Bundesgericht zieht in Erwägung:
1. Das Bundesgesetz über das Bundesgericht vom 17. Juni 2005 (BGG; SR 173.110) ist am 1. Januar 2007 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> E. 1.2 S. 395).
2. Gemäss <ref-law> können die Versicherten unter den zugelassenen Leistungserbringern, die für die Behandlung ihrer Krankheit geeignet sind, frei wählen. Diese freie Wahl des Leistungserbringers wird im Rahmenvertrag gestützt auf <ref-law> sowie die Asylverordnung 2 vom 11. August 1999 über Finanzierungsfragen (AsylV 2; SR 142.312) eingeschränkt.
Nach <ref-law> können die Versicherten ihr Wahlrecht im Einvernehmen mit dem Versicherer auf Leistungserbringer beschränken, die der Versicherer im Hinblick auf eine kostengünstigere Versorgung auswählt (Art. 62 Abs. 1 und 3 KVG). Der Versicherer muss dann nur die Kosten für Leistungen übernehmen, die von diesen Leistungserbringern ausgeführt oder veranlasst werden; Absatz 2 gilt sinngemäss. Die gesetzlichen Pflichtleistungen sind in jedem Fall versichert.
Art. 26 Abs. 4 AsylV 2 lautet: Die Kantone schränken für Asylsuchende, vorläufig Aufgenommene und Schutzbedürftige ohne Aufenthaltsbewilligung die Wahl des Versicherers und der Leistungserbringer ein, namentlich in Fällen, in denen zwischen Versicherungen und Leistungserbringern Vereinbarungen nach den Artikeln 42 Absatz 2 und 62 KVG abgeschlossen worden sind. Die Kantone haben die geeigneten Massnahmen zu ergreifen, um die Qualität des Leistungsangebotes sicherzustellen. Im Übrigen gilt Artikel 41 Absatz 4 KVG sinngemäss.
3. Es ist unbestritten, dass der Beschwerdegegner nicht auf der Asyl-Hausarztliste (Ziff. 5.3 Rahmenvertrag) figuriert und K._ zur Zeit der streitigen Behandlung unter die Bestimmungen des Rahmenvertrags fiel. Vorinstanz und Beschwerdegegner sind jedoch der Ansicht, die im Rahmenvertrag vorgesehene Beschränkung der Wahl der Leistungserbringer (Ziff. 4.2 Rahmenvertrag) widerspreche <ref-law>. Sie lasse sich weder auf <ref-law> noch auf Art. 26 Abs. 4 AsylV 2 stützen. Die erstgenannte Bestimmung könne nicht als Grundlage dienen, weil dem Versicherten beim Abschluss und bei der Ausgestaltung des Versicherungsverhältnisses kein Mitspracherecht zuerkannt worden sei, dieser somit nicht im Sinne dieser Norm sein Wahlrecht habe beschränken können. Auch die zweitgenannte Norm vermöge die im Rahmenvertrag vorgesehene Einschränkung der Wahlmöglichkeit nicht zu rechtfertigen, da sie keine genügende formellgesetzliche Grundlage habe.
4. 4.1 Der Rahmenvertrag gilt gemäss seiner Ziffer 2 nicht generell für Asylsuchende, vorläufig Aufgenommene und Schutzbedürftige ohne Aufenthaltsbewilligung, sondern ausschliesslich für diejenigen Personen dieser Kategorien, welche von den zuständigen Fürsorgebehörden unterstützt werden; für fürsorgeunabhängige Personen gilt er ausdrücklich nicht. Gemäss Ziff. 3.4 des Rahmenvertrags endet die damit geschlossene Versicherung denn auch, wenn die Unterstützung der versicherten Person durch die zuständige Fürsorgebehörde entfällt.
Auch Art. 26 Abs. 4 AsylV 2 betrifft - im Kontext gelesen - nicht generell die Krankenversicherung der betreffenden Personen, sondern einzig die Fürsorgeleistungen, welche für diese Personen in Bezug auf die medizinische Versorgung erbracht werden, bzw. die Vergütung, die der Bund den Kantonen dafür leistet (Art. 88 ff., namentlich <ref-law> sowie Art. 26 Abs. 1 und 2 AsylV 2).
Bei dieser Sachlage - namentlich auch mit Blick darauf, dass von keiner Seite behauptet wird, K._ sei im fraglichen Zeitpunkt nicht von der Fürsorge unterstützt worden - ist nicht streitig, ob der Kanton generell für Asylsuchende die freie Wahl der Leistungserbringer einschränken darf, sondern wie er die Fürsorgeleistungen für diese Personen auszugestalten hat.
4.2 Die Fürsorge bzw. Sozialhilfe gewährleistet nicht das Leistungsniveau, das sich fürsorgeunabhängige Personen aus eigenen Mitteln leisten könnten und dürften. So bezahlt die Fürsorge beispielsweise nicht überhöhte Wohnkosten oder Kosten für nicht benötigte Fahrzeuge (vgl. <ref-ruling>, nicht publ. E. 6; Felix Wolffers, Grundriss des Sozialhilferechts, 2. A., Bern 1999, S. 142 f.). Solche Leistungsbegrenzungen sind dem Wesen der Sozialhilfe immanent und stellen keine Einschränkung des sich aus der Vertragsfreiheit ergebenden Rechts dar, luxuriöse Wohnungen oder Autos zu kaufen. Erst recht wird dadurch nicht die Wirtschaftsfreiheit der Anbieter von Wohnungen oder Autos eingeschränkt. Desgleichen kann beispielsweise das fürsorgepflichtige Gemeinwesen vom Fürsorgeempfänger verlangen, dass er soweit zumutbar eine Erwerbstätigkeit ausübt (<ref-ruling> E. 4.3 S. 75 f.; Wolffers, a.a.O., S. 108 ff.); dabei handelt es sich nicht etwa um eine hoheitliche Arbeitsverpflichtung, sondern um eine Anspruchsvoraussetzung für die vom Staat erbrachte Leistung (Kathrin Amstutz, Anspruchsvoraussetzungen und -inhalt, in: Carlo Tschudi [Hrsg.], Das Grundrecht auf Hilfe in Notlagen, Bern 2005, S. 17 ff., 23 f.). Analoges gilt auch im Bereich der Fürsorgekosten für die medizinische Versorgung bzw. Krankenversicherung: Das fürsorgepflichtige Gemeinwesen muss nicht eine kostspielige Versorgung oder Krankenversicherung finanzieren, wenn auch mit einer kostengünstigeren Lösung eine ausreichende medizinische Versorgung sichergestellt ist. So kann beispielsweise vom Sozialhilfeempfänger verlangt werden, sich nur beim Hausarzt oder durch vom Hausarzt zugezogene Spezialisten behandeln zu lassen oder vor der Konsultation die Bewilligung der Sozialhilfebehörde einzuholen (Wolffers, a.a.O., S. 146; vgl. ähnlich auch Art. 8 Abs. 3 ELKV). Es geht dabei nicht um das Recht der versicherten Personen, den Arzt frei zu wählen, und auch nicht um das Recht der Leistungserbringer auf Ausübung ihrer Wirtschaftsfreiheit, sondern um die Ausgestaltung der vom Staat zu erbringenden Fürsorgeleistungen.
4.3 Gemäss <ref-law> gewährleisten die Kantone die Fürsorge für Personen, die sich gestützt auf dieses Gesetz in der Schweiz aufhalten. Für die Ausrichtung von Fürsorgeleistungen gilt grundsätzlich kantonales Recht (<ref-law>), wobei jedoch mit Rücksicht auf die weitgehende Bundesfinanzierung (<ref-law>) auch die im Asylgesetz enthaltenen bundesrechtlichen Regeln zu beachten sind (Bernhard Waldmann, Das Recht auf Nothilfe zwischen Solidarität und Eigenverantwortung, ZBl 2006 S. 341 ff., 364).
Das Asylgesetz unterscheidet zwischen Asylsuchenden und Schutzbedürftigen ohne Aufenthaltsbewilligung einerseits sowie Flüchtlingen und Schutzbedürftigen mit Anspruch auf Aufenthaltsbewilligung andererseits. Diese Unterscheidung rechtfertigt sich dadurch, dass die Angehörigen der ersten Kategorie nur ein vorübergehendes Aufenthaltsrecht in der Schweiz haben. Die an sie erbrachten Fürsorgeleistungen sind demnach nicht auf die Integration ausgerichtet; daraus ergibt sich die Berechtigung, Asylsuchende und Schutzbedürftige ohne Aufenthaltsbewilligung nicht nur anders, sondern auch in geringerem Umfang als andere Personen zu unterstützen (Botschaft des Bundesrats vom 4. Dezember 1995 zur Änderung des Asylgesetzes, BBl 1996 II 1 ff., 89 f.; <ref-ruling> E. 7.2.1 S. 180 und E. 8.2 S. 181 ff., 130 I 1 E. 3.6.1 S. 11 f.). Die Unterstützung ist nach Möglichkeit in Form von Sachleistungen auszurichten (<ref-law>). Dies betrifft insbesondere auch den Versicherungsschutz bei Krankheiten (BBl 1996 II 89).
Bei dieser Rechtslage liegt eine genügende formellgesetzliche Grundlage für eine von der Regelung der ordentlichen Fürsorgeleistung abweichende Normierung vor (<ref-ruling> E. 3.6.3 S. 13). Entgegen der Auffassung der Vorinstanz findet auch Art. 26 Abs. 4 AsylV 2 in <ref-law> eine genügende formellgesetzliche Grundlage. Die Tatsache, dass eine analoge Regelung inzwischen auf die Stufe des formellen Gesetzes gehoben worden ist (<ref-law> in der noch nicht in Kraft getretenen Fassung gemäss Revision des KVG vom 16. Dezember 2005, AS 2006 4823 f.), bedeutet nicht, dass die gesetzliche Grundlage vorher ungenügend gewesen wäre.
4.4 Die krankenversicherungspflichtigen Asylsuchenden (Art. 3 Abs. 1 [vgl. <ref-ruling>] oder <ref-law> in Verbindung mit <ref-law>) müssen sich zwar grundsätzlich selber versichern (<ref-law>). Wenn aber das fürsorgepflichtige Gemeinwesen gemäss <ref-law>, welche Bestimmung sowohl als lex posterior als auch als lex specialis dem KVG vorgeht, die Fürsorge nach Möglichkeit in Form von Sachleistungen zu erbringen hat, kann es für die und an Stelle der grundsätzlich versicherungspflichtigen Fürsorgeempfänger eine Krankenversicherung abschliessen. Es stellt damit den Versicherungsschutz als Sachleistung zur Verfügung. Das gilt zumindest dann, wenn - wie das hier unbestritten der Fall ist - der Versicherte nicht selber bereits eine andere Versicherung abgeschlossen hat (vgl. <ref-ruling> E. 3b S. 268 f.).
4.5 In diesem Sinne hat die Direktion für Soziales und Sicherheit des Kantons Zürich als Versicherungsnehmerin den Rahmenvertrag abgeschlossen, welcher gemäss Art. 26 Abs. 4 AsylV 2 eine Einschränkung der freien Wahl des Leistungserbringers im Sinne von Art. 41 Abs. 4 und Art. 62 KVG vorsieht. Mit diesem Vertrag sorgt der Kanton für die Versicherung der betroffenen Fürsorgeempfänger und bezahlt gestützt darauf dem Versicherer die Prämien, Franchisen und Selbstbehalte (Anhang 5 Ziff. 3 Rahmenvertrag). Dabei handelt es sich nicht um einen in der Grundversicherung nicht mehr zulässigen eigentlichen Kollektivvertrag; vielmehr ist darin die Erbringung der angemessenen Fürsorgeleistung in Sachleistungsform gemäss <ref-law> geregelt. Der Kanton Zürich ist damit seiner Fürsorgepflicht rechtmässig nachgekommen.
5. Der Beschwerdegegner macht geltend, er sei willkürlich von der Asyl-Hausarztliste ausgeschlossen und damit in seiner Wirtschaftsfreiheit als Leistungserbringer verletzt worden.
5.1 Nach dem in E. 4 Gesagten kann eine allfällige Verletzung der Wirtschaftsfreiheit des Beschwerdegegners nicht schon darin liegen, dass der Rahmenvertrag die Wahl der Leistungserbringer einschränkt, sondern höchstens darin, dass der Beschwerdegegner nicht auf die Asyl-Hausarztliste aufgenommen wurde.
5.2 Gemäss Ziff. 5.3 des Rahmenvertrags werden die Leistungserbringer gemeinsam von den Vertragspartnern aus einer durch die Ärztegesellschaft erstellten Liste bestimmt. Das (damalige) Eidgenössische Versicherungsgericht hat in E. 5 des Urteils K 66/02 vom 17. August 2004 festgehalten, dass der Beschwerdegegner beim Schiedsgericht gemäss <ref-law> eine Gestaltungsklage auf Aufnahme in die Asyl-Hausarztliste einreichen könne. In jenem Verfahren wäre zu prüfen, ob sich allenfalls aus der Wirtschaftsfreiheit ein Anspruch auf Aufnahme in diese Liste ergeben könnte. Die Verfügungs-, Einsprache- und Beschwerdeinstanzen nach Art. 80, 85 und 86 KVG bzw. Art. 49, 52 und 56 ff. ATSG sind deshalb nicht zuständig, über diese Frage zu befinden. Nichts anderes ergäbe sich, wenn der Entscheid über die Aufnahme oder Nichtaufnahme auf die Ärzteliste durch ein staatliches Organ getroffen würde; in diesem Fall wäre der Entscheid auf dem dafür vorgesehenen Rechtsweg anfechtbar und könnte jedenfalls nicht vom Krankenversicherer verfügungsweise in Frage gestellt werden. Die Vorinstanz hat sich deshalb zu dieser Frage mit Recht nicht geäussert. Unter diesen Umständen ist auf die Rüge, die Nichtaufnahme des Beschwerdegegners in die Liste sei verfassungswidrig, nicht näher einzugehen.
6. Das Verfahren ist kostenfrei (Art. 134 OG). Die obsiegende Beschwerdeführerin hat keinen Anspruch auf Parteientschädigung (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. In Gutheissung der Verwaltungsgerichtsbeschwerde wird der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 30. November 2006 aufgehoben.
2. Es werden keine Gerichtskosten erhoben.
3. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Gesundheit zugestellt.
Luzern, 13. Juni 2007
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: