Faits:
A. F._, né en 1980, de nationalité française, domicilié à B._ (France), travaille en qualité de conducteur de travaux au service de la société T._, à A._. En cette qualité, il est obligatoirement assuré contre les accidents professionnels et non professionnels auprès de la Caisse nationale suisse d'assurance en cas d'accidents (CNA). La caisse-maladie Q._ l'assure pour la perte de gain en cas de maladie. En ce qui concerne les soins en cas de maladie, il a opté, en tant que travailleur frontalier, pour l'application de la législation française. A ce titre, il était affilié auprès de L._ du 1er décembre 2004 au 27 novembre 2005, puis auprès de M._ depuis le 28 novembre 2005.
Le 27 octobre 2005, au cours d'un match de rugby, il a ressenti des douleurs rachidiennes. Il a néanmoins travaillé le lendemain. Le 2 novembre suivant, il a consulté son médecin traitant, à B._. Par déclaration d'accident-bagatelle LAA, son employeur a annoncé le cas à la CNA, qui lui a remboursé diverses consultations médicales en France. F._ a été incapable de travailler dès le 19 novembre 2005. Son médecin traitant, le docteur R._, a posé le diagnostic de syndrome radiculaire C7 gauche avec présence d'une hernie discale C6-C7 gauche. Le 16 janvier 2006, en réponse à un questionnaire de la CNA, l'intéressé a fourni des précisions en vue de compléter la déclaration d'accident. Il a précisé qu'au cours du match en question, qu'il a qualifié de « physique », il avait ressenti des douleurs à la fin du match. Celles-ci s'étaient accentuées au fur et à mesure du refroidissement des muscles.
Le 15 mars 2006, le Service de neurologie de l'Hôpital X._ a communiqué à la CNA divers documents concernant l'assuré en précisant que l'état de celui-ci nécessiterait une intervention neurochirurgicale. Le 21 mars 2006, F._ a eu un entretien avec un représentant de la CNA, à W._. Il a fourni divers renseignements concernant sa formation, son activité professionnelle, ses antécédents et sa couverture d'assurance en France. Il est revenu sur les circonstances qui avaient provoqué le déclenchement de ses douleurs rachidiennes. Enfin, il a indiqué que l'intervention chirurgicale, qui consisterait en l'ablation du disque et la mise en place d'une prothèse, aurait lieu le 28 mars 2006 à l'Hôpital X._. L'intervention a été pratiquée à la date prévue.
Par décision du 30 mars 2006, confirmée par décision sur opposition du 20 juin suivant, la CNA a refusé de prendre en charge le cas, au motif que l'événement annoncé ne présentait pas les caractéristiques d'un accident et ne répondait pas non plus à la notion de lésion corporelle assimilée à un accident. Elle a exigé le remboursement de 282 EUR 15 pour des frais de traitement qu'elle avait assumés.
Q._ a versé les indemnités journalières en raison de l'incapacité de travail.
B. Statuant le 24 septembre 2008, le Tribunal des assurances du canton de Vaud a rejeté le recours formé par l'assuré contre la décision sur opposition de la CNA.
C. F._ a formé un recours en matière de droit public et un recours constitutionnel subsidiaire dans lequel il a conclu à la réforme du jugement cantonal en ce sens que la CNA soit condamnée à prendre en charge les suites de l'événement du 27 octobre 2005 « libre à elle de régler compte, cas échéant, avec des institutions d'assurances françaises concernées ». Il a produit un avis de droit de la professeure J._.
La CNA a conclu au rejet du recours. L'Office fédéral des assurances sociales (OFAS), domaine des affaires internationales, a déposé un préavis dans lequel il a proposé le rejet du recours. Les parties ont maintenu leurs conclusions au terme d'un nouvel échange d'écritures; le recourant a déposé un avis de droit complémentaire.
Considérant en droit:
1. La voie du recours en matière de droit public est ouverte, la décision attaquée ayant été rendue dans une cause de droit public (art. 82 let. a LTF), sans que l'une des exceptions de l'art. 83 LTF ne soit réalisée. Le jugement attaqué pouvant ainsi faire l'objet d'un recours en matière de droit public, la voie du recours constitutionnel subsidiaire, également formé par le recourant est irrecevable (art. 113 LTF).
2. A lire le mémoire de recours, il apparaît que le recourant demande uniquement la prise en charge par la CNA de frais de traitement, notamment des frais de traitement et d'hospitalisation à l'Hôpital X._ (de l'ordre de 20'000 fr.). Le jugement attaqué ne concerne donc pas l'octroi ou le refus de prestations en espèces de l'assurance-accidents (art. 105 al. 3 LTF). Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Il ne peut rectifier ou compléter d'office les constatations de l'autorité précédente que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF).
3. A l'instar de la CNA, les premiers juges ont retenu que l'atteinte à la santé apparue le 27 octobre 2005 n'était pas consécutive à un accident. Cette atteinte ne pouvait pas non plus être considérée comme une lésion corporelle assimilée à un accident. Ces deux points ne sont plus contestés devant le Tribunal fédéral. Le droit aux prestations litigieuses ne peut donc pas être déduit de la LAA (art. 6 al. 1 LAA; art. 6 al. 2 LAA en corrélation avec l'art. 9 al. 2 OLAA).
4. Le recourant fonde sa prétention, principalement, sur les règles de coordination de l'Accord sur la libre circulation des personnes et sur les règlements communautaires en matière de sécurité sociale. C'est donc sous cet angle qu'il convient, en premier lieu, d'examiner le litige.
4.1 L'Accord sur la libre circulation des personnes (ALCP) est entré en vigueur le 1er juin 2002. Selon l'art. 1 par. 1 de l'Annexe II « Coordination des systèmes de sécurité sociale » de l'accord, fondée sur l'art. 8 ALCP et faisant partie intégrante de celui-ci (art. 15 ALCP), en relation avec la Section A de cette Annexe, les Parties contractantes appliquent entre elles, en particulier, le Règlement (CEE) no 1408/71 du Conseil du 14 juin 1971 relatif à l'application des régimes de sécurité sociale aux travailleurs salariés, aux travailleurs non salariés et aux membres de leur famille qui se déplacent à l'intérieur de la Communauté (règlement no 1408/71), ainsi que le Règlement (CEE) no 574/72 du Conseil du 21 mars 1972 fixant les modalités d'application du Règlement (CEE) no 1408/71 relatif à l'application des régimes de sécurité sociale aux travailleurs salariés, aux travailleurs non salariés et aux membres de leur famille qui se déplacent à l'intérieur de la Communauté (règlement no 574/72) ou des règles équivalentes.
4.2 Cette réglementation est applicable au recourant du point de vue personnel: de nationalité française, l'intéressé doit être considéré comme un travailleur qui est ou était soumis à la législation d'un ou de plusieurs Etats membres (art. 2 par. 1 du règlement no 1408/71). Il en va de même de l'applicabilité de l'accord et des règlements cités sous l'angle matériel. Les prestations litigieuses se rapportent à l'un des risques énumérés expressément à l'art. 4 par. 1 du règlement no 1408/71, en l'occurrence la lettre a (prestations de maladie et de maternité).
4.3 S'agissant d'une relation transfrontalière, il s'agit tout d'abord d'examiner la question du droit applicable en matière d'assurance-maladie.
4.3.1 Le Titre II du règlement no 1408/71 (art. 13 à 17bis) contient des règles qui permettent de déterminer la législation applicable pour toute la généralité des cas. L'art. 13 par. 1 énonce le principe de l'unicité de la législation applicable en fonction des règles contenues aux art. 13 par. 2 à 17bis, dans le sens de l'applicabilité de la législation d'un seul Etat membre. En principe, le travailleur salarié est soumis à la législation de son Etat d'occupation salariée, même s'il réside sur le territoire d'un autre Etat membre ou si l'entreprise ou l'employeur qui l'occupe a son siège ou son domicile sur le territoire d'un autre Etat membre. Le travailleur frontalier est donc soumis, en vertu de ce principe, à la législation de l'Etat où il travaille (principe de la lex loci laboris); l'Etat compétent est l'Etat d'emploi (art. 13 par. 2 let. a du règlement no 1408/71; ATF 133 V 137 consid. 6.1 p. 143; PRODROMOS MAVRIDIS, La sécurité sociale à l'épreuve de l'intégration européenne : étude d'une confrontation entre libertés du marché et droits fondamentaux, Athènes et Bruxelles 2003, p. 488 no 473).
4.3.2 Ce principe peut être assorti d'exceptions. En effet, en application de l'art. 89 du règlement no 1408/71, l'Annexe VI audit règlement régit les modalités particulières d'application des législations de certains Etats membres. Cette annexe a été complétée par la Section A de l'Annexe II à l'ALCP « Coordination des systèmes de sécurité sociale ». Il en ressort notamment que les personnes soumises aux dispositions légales suisses peuvent, sur demande, être exemptées de l'assurance-maladie obligatoire (LAMal) en tant qu'elles résident dans l'un des Etats suivants et peuvent prouver qu'elles y bénéficient d'une couverture en cas de maladie: Allemagne, Autriche, France, Italie et, dans certains cas, la Finlande et le Portugal (Annexe II Section A par. 1 let. o ch. 3 b, dans sa version modifiée par les décisions no 2/2003 et 1/2006 du Comité mixte UE-Suisse des 15 juillet 2003 et 6 juillet 2006 [RO 2004 1277 et RO 2006 5851]). Cette faculté est communément appelée « droit d'option » (cf. aussi BETTINA KAHIL-WOLFF/CORINNE PACIFICO, Sécurité sociale, droit du travail et fiscalité: le droit applicable en cas de situations transfrontalières, in : Assujettissement, cotisations et questions connexes selon l'Accord sur la libre circulation des personnes CH-CE, Berne 2004, p. 37 s.).
4.3.3 Cette réglementation sur le droit d'option n'exige pas une couverture équivalente auprès d'un organisme d'assurance de droit public; il peut également s'agir d'une assurance conclue auprès d'un assureur privé.
Il est à relever dans ce contexte que jusqu'au 1er juin 2002 les relations entre la Suisse et la France en matière de sécurité sociale étaient régies par la convention franco-suisse du 3 juillet 1975. Les travailleurs frontaliers n'avaient alors pas l'obligation de s'affilier à la LAMal, faute de domicile en Suisse (art. 3 LAMal), mais ils en avaient la faculté (art. 3 OAMal). Lors des négociations de l'ALCP, les autorités françaises n'ont pas souhaité l'introduction d'un droit d'option, car cela revenait à remettre en cause le principe de l'unicité de la législation applicable. Elles sont revenues sur cette position de principe après avoir été saisies par le Groupement transfrontalier européen - dont la vocation est de veiller à l'intérêt des populations transfrontalières - d'un rapport insistant sur l'importance du droit d'option pour les travailleurs frontaliers. Sur la base des conclusions d'une expertise indépendante, le gouvernement français s'est engagé dans un premier temps à accepter un droit d'option, mais en faveur seulement des régimes nationaux (LAMal ou couverture maladie universelle [CMU] selon la loi française du 27 juillet 1999). Comme une majorité de travailleurs frontaliers se trouvait alors au bénéfice d'un contrat d'assurance privé, le gouvernement a finalement admis que le choix pouvait aussi se porter sur des opérateurs privés en cas d'option pour la couverture d'assurance en France (voir à ce sujet: GUYLAINE RIONDEL BESSON, La sécurité sociale des travailleurs frontaliers dans le cadre de l'Accord sur la libre circulation des personnes, signé entre la Suisse et la Communauté européenne: l'exemple de l'assurance-maladie maternité, in : Cahiers genevois et romands de sécurité sociale, 30/2003, p. 25 s.). La législation française a été modifiée en conséquence par l'adjonction dans le code de la sécurité sociale d'un article L. 380-3-1. Cet article pose le principe de l'affiliation obligatoire au régime de base de la sécurité sociale (CMU) des travailleurs frontaliers qui ont demandé à être exemptés de l'affiliation au régime suisse d'assurance-maladie. Il prévoit cependant, pour une période transitoire, se terminant au plus tard le 1er juin 2014 (selon l'actuelle version de cette disposition), que les intéressés peuvent conserver un contrat d'assurance privé, les couvrant en France, ainsi que leurs ayants droit, pour le risque de maladie et de maternité (voir RIONDEL BESSON, loc. cit., p. 30 s.; de la même auteure: Le droit d'option en matière d'assurance-maladie dans le cadre de l'Accord sur la libre circulation des personnes : difficultés de mise en oeuvre et conséquences pour les assurés, in : Cahiers genevois et romands de sécurité sociale, 42/2009, p. 33 ss).
4.3.4 En fonction de ce droit d'option, les personnes qui résident en France et qui travaillent en Suisse peuvent ainsi être couvertes soit en Suisse soit en France. Elles ont le choix entre le régime d'assurance-maladie suisse selon la LAMal, le régime de la CMU et (pour une période transitoire) l'assurance privée en France. C'est donc en application de la réglementation précitée que le recourant - travaillant en Suisse et résidant en France - a demandé et obtenu l'exemption de l'assurance-maladie obligatoire en Suisse selon la LAMal au profit d'une couverture d'assurance privée.
4.4 La question est maintenant de savoir si le recourant peut déduire un droit au remboursement, même provisoire, par la CNA (ou par une autre institution compétente suisse) des frais de traitement litigieux en se fondant sur les règles générales de coordination européenne en matière d'assurance-maladie.
4.4.1 La personne qui - à l'instar du recourant - travaille en Suisse et a opté pour la législation de l'Etat de résidence en ce qui concerne l'assurance-maladie reste assurée aux autres assurances sociales suisses, notamment à la LAA (art. 1a LAA).
Il est largement admis que les art. 18 à 36 du règlement no 1408/71 (chap. 1), qui concernent les éventualités maladie et maternité, englobent les prestations pour soins accordées pour les accidents non professionnels (BETTINA KAHIL-WOLFF, La coordination européenne des systèmes nationaux de sécurité sociale, in : Schweizerisches Bundesverwaltungsrecht [ SBVR], Soziale Sicherheit, 2ème éd., Bâle 2007, p. 200 no 74; GEBHARD EUGSTER, Krankenversicherung, in : SBVR, Soziale Sicherheit, p. 565 s. no 494; JEAN-MAURICE FRÉSARD/MARGIT MOSER-SZELESS, L'assurance-accidents obligatoire, in : SBVR, Soziale Sicherheit, p. 927 no 282 et no 283; SERAINA ROHNER, L'Accord et l'assurance-accidents selon la LAA: accord sur la libre circulation des personnes, in : Sécurité sociale 2/2002 p. 85 s.; EDGAR IMHOf, Eine Anleitung zum Gebrauch des Personenfreizügigkeitsabkommens und der VO 1408/71 : insbesondere eine Darstellung der besonderen Vorschriften der VO 1408/71 über die einzelnen Leistungszweige, in : Aktuelles im Sozialversicherungsrecht, Zurich 2001, p. 75; contra: PATRICIA USINGER-EGGER, Die Unfallversicherung und ihre Auslandwirkung, RSAS 2008 p. 253 ss, qui considère que les prestations de la LAA pour les accidents non professionnels sont dans l'ensemble soumises au chapitre 4 du règlement 1408/71, relatif aux accidents du travail et aux maladies professionnelles).
Par conséquent, si la personne en question est victime d'un accident non professionnel, elle pourrait prétendre des prestations en nature de l'assurance-accidents suisse (au titre de la LAA) et de l'organisme compétent dans son Etat de résidence (au titre de l'assurance-maladie). Dans cette éventualité, les coûts des prestations en nature sont répartis pour moitié entre l'assureur suisse LAA et l'institution de l'assurance-maladie de l'autre Etat (Annexe II Section A par. 1 let. o ch. 3bis ALCP; voir aussi KAHIL-WOLFF, op. cit., p. 206 no 84). Cette éventualité n'entre pas en considération en l'espèce. Elle suppose un droit à des prestations des deux organismes. Or, le recourant - cela est incontesté - n'a pas droit à des prestations de la CNA en application de la LAA (supra consid. 3).
4.4.2 Le chapitre I («Maladie et maternité») du Titre III («Dispositions particulières aux différentes catégories de prestations») du règlement no 1408/71 contient des règles d'entraide visant à faciliter l'accès aux soins et aux prestations en espèces lors du séjour ou de la résidence en dehors de l'Etat compétent (soit l'Etat dans lequel l'intéressé est assuré). En ce qui concerne plus précisément les prestations en nature, qui sont en discussion ici, ces règles prévoient une répartition des tâches entre l'institution de l'Etat de résidence ou de l'Etat de séjour et l'Etat compétent selon les principales modalités suivantes:
a) En cas de résidence sur le territoire d'un Etat membre autre que l'Etat compétent, le travailleur (salarié ou non salarié) a droit à des prestations en nature servies - pour le compte de l'institution compétente - par l'institution du lieu de résidence, selon les dispositions de la législation que celle-ci applique (art. 19 par. 1 let. a du règlement 1408/71). Les travailleurs frontaliers peuvent également obtenir les prestations sur le territoire de l'Etat compétent; ces prestations sont servies par l'institution compétente selon les dispositions de la législation de cet Etat, comme si l'intéressé résidait dans celui-ci (art. 20 du règlement 1408/71).
b) En cas de séjour en dehors de l'Etat compétent, l'intéressé qui satisfait aux conditions requises par la législation de l'Etat compétent et dont l'état vient à nécessiter des prestations en nature nécessaires du point de vue médical a droit aux prestations en nature servies - pour le compte de l'institution compétente - par l'institution du lieu de séjour (art. 22 par. 1 let. a, dans sa version modifiée par le règlement no 631/2004, et applicable dans les relations entre la Suisse et l'Union européenne en vertu de la décision précitée no 1/2006 du Comité mixte UE-Suisse). Cette disposition est aussi applicable aux personnes qui travaillent mais ne résident pas en Suisse et qui sont affiliées à l'assurance-maladie légale de leur Etat de résidence, pour tout état venant à nécessiter des prestations lors d'un séjour en Suisse (Annexe II Section A par. 1 let. o ch. 3ter ALCP introduit par la décision 2/2003 du Comité mixte). Il s'agit d'un accès facilité aux soins pour les personnes qui ont fait le choix de s'assurer au régime (légal) de la CMU (RIONDEL BESSON, L'évolution de la prise en charge des soins de santé à l'étranger dans le cadre des relations communautaires, in : Cahiers genevois et romands de sécurité sociale, 32/2004, p. 122 s.)
Sous réserve de cette dernière éventualité (état venant à nécessiter des prestations lors d'un séjour en Suisse), qui n'entre pas en considération ici (l'opération en Suisse était programmée et, de surcroît, l'intéressé n'était pas affilié à la CMU), le système d'entraide tel que décrit plus haut est inopérant en l'espèce. Il ne se conçoit en effet que dans le régime ordinaire d'affiliation à la lex loci laboris (cf. FRANCIS KESSLER/JEAN-PHILIPPE LHERNOULD, Code annoté européen de la protection sociale, 3e éd. Paris 2005, p. 155). De même, selon l'art. 20 précité du règlement, les travailleurs frontaliers assujettis à la LAMal (Etat d'occupation) peuvent aussi obtenir des prestations sur le territoire de l'Etat compétent (en l'occurrence la Suisse). Mais cette disposition est sans pertinence lorsque le travailleur frontalier a opté pour l'assurance de son Etat de résidence. Dans ce cas, en effet, l'Etat compétent et l'Etat de résidence coincident et il n'y a donc pas matière à coordination des prestations d'assurance-maladie (cf. également GEBHARD EUGSTER, op. cit., p. 423 no 74). La coordination se limite ici à l'accès facilité aux soins selon la décision susmentionnée 2/2003.
4.4.3 En conséquence, les règles de coordination européenne telles que décrites n'imposent pas, en l'espèce, une prise en charge des frais de traitement litigieux par une institution suisse d'assurance. Le recourant, du reste, ne prétend pas le contraire.
5. 5.1 Le recourant fait cependant valoir qu'il pâtit d'un conflit négatif de compétences, quand bien même il a régulièrement payé des cotisations visant à l'assurer contre les conséquences de la maladie et de l'accident, en Suisse comme en France. Le droit d'option instauré par l'ALCP conduit à une lacune en ce qui concerne l'entraide. Le but du règlement, qui est de garantir une prise en charge, au moins provisoire, au profit des travailleurs migrants est totalement manqué si l'assureur LAA et l'assureur-maladie refusent tous les deux, de manière non concertée, de prendre en charge un traitement. Selon lui, il convient d'interpréter les règlements no 1408/71 et no 574/72 sous un angle téléologique soit au regard du but de l'ALCP. Sous cet angle il eût appartenu à la CNA, qui est l'organisme de liaison pour l'assurance-accidents, de prendre en charge le traitement litigieux et d'entreprendre au besoin les démarches nécessaires en vue de se faire rembourser par l'assureur privé.
5.2 On relèvera tout d'abord ici que la CNA n'est un organisme de liaison que pour les accidents du travail et les maladies professionnelles. Pour les accidents non professionnels (qui relèvent de la maladie; supra consid. 4.4.1), l'organe de liaison est l'Institution commune LAMal (Annexe II Section A par. 2 let. c ch. 4 et let. d ch. 1 ALCP). Il n'y a cependant pas lieu d'examiner plus avant si le recourant aurait dû en réalité s'adresser à cette institution. Son argumentation tirée d'une lacune dans le système d'entraide européen est, comme on va le voir, de toute façon mal fondée.
5.3 Un mécanisme de coopération judiciaire sous la forme notamment d'un renvoi préjudiciel à la Cour de justice des communautés européennes n'existe pas entre la Suisse et la Communauté européenne et ses Etats membres. Confronté à un problème d'interprétation, le juge suisse n'a donc ni l'obligation ni même la possibilité de se référer à la Cour de justice mais doit le résoudre seul, en se conformant aux règles d'interprétation habituelles déduites de la Convention de Vienne du 23 mai 1969 sur le droit des traités (ATF 130 II 113 consid. 6.1 p. 120 s.). Pour ce qui est de l'interprétation des accords internationaux, la Convention de Vienne (RS 0.111) pose des principes directeurs, qui sont relativement semblables aux méthodes d'interprétation valant pour les normes générales et abstraites que la jurisprudence fédérale a consacrées (ATF 130 I 312 consid. 4.1 in fine p. 326; 130 II 113 consid. 6.1 in fine p. 121). Ainsi, l'art. 31 par. 1 de cette convention prescrit que le traité doit être interprété de bonne foi suivant le sens ordinaire à attribuer aux termes du traité dans leur contexte et à la lumière de son objet et de son but. Quant à l'art. 32 par. 1 in initio, il précise qu'il peut être fait appel à des moyens complémentaires d'interprétation, notamment aux travaux préparatoires, en vue soit de confirmer le sens résultant de l'application de l'art. 31, soit de déterminer le sens lorsque l'interprétation donnée conformément à ces dispositions laisse en particulier le sens ambigu ou obscur (let. a). Il n'appartient toutefois pas au juge de remédier par voie d'interprétation à une éventuelle lacune d'un traité international, en étendant l'application de celui-ci au-delà de son texte. Une telle application extensive n'entrerait en ligne de compte que si l'on pouvait déduire avec certitude du contexte ou de la genèse du traité que l'expression de la volonté des parties à la convention est inexacte (voir ATF 119 V 98 consid. 6a p. 107; 117 V 268 consid. 3b p. 269).
5.4 Tel n'est pas le cas en l'espèce. Comme on l'a vu, l'exercice du droit d'option exclut, par principe, une coordination des prestations de l'assurance-maladie par le biais de l'entraide instituée par les art. 19 ss du règlement no 1408/71 (sous réserve d'un état venant à nécessiter des prestations lors d'un séjour en Suisse). Cette absence de coordination est le corollaire de l'exemption de l'assurance obligatoire en Suisse. Par ailleurs, les Parties contractantes admettent une exemption de l'assujettissement à l'assurance-maladie suisse en cas de couverture équivalente non seulement auprès d'un organisme de droit public, mais également auprès d'un assureur privé. Cette dernière faculté comporte, il est vrai, certains risques pour l'intéressé, en ce sens qu'elle peut conduire à des lacunes d'assurance. Ainsi, les contrats d'assurance privés peuvent être résiliés en cas de retard dans le paiement des primes ou encore en cas de réticence. Le contrat d'assurance peut aussi prévoir des clauses d'exclusion qui ne sont généralement pas admissibles dans un régime de couverture d'assurance régi par le droit public (EUGSTER, op. cit., p. 423 no 74). La présente cause est une illustration de ce risque. Selon une lettre de Y._ à l'assuré du 31 août 2006, le refus par l'assurance privée de prendre en charge les frais d'hospitalisation à l'Hôpital X._ est motivé par le fait que la prise en charge d'un traitement chirurgical est soumise à «entente préalable», que la prise en charge en Suisse est «hors contrat» et que la hernie discale est considérée par les experts français comme un accident dans les «trois premiers mois». Pour autant, ce n'est pas à l'institution de l'Etat dont la personne, précisément, est exemptée de l'assurance obligatoire, d'assumer les conséquences de ce risque. Cela reviendrait, dans les faits, à créer à la charge de cet Etat une assurance subsidiaire destinée à combler des lacunes de couverture ou à compléter une couverture d'assurance insuffisante ou encore à prendre en charge des prestations pour des affections faisant l'objet d'une réserve. Cette subsidiarité ne relève pas de la coordination des prestations selon le droit communautaire tel qu'il est aménagé dans les relations franco-suisses. Le fait que la CNA a alloué dans un premier temps des prestations avant de les refuser en raison de l'absence d'un événement accidentel ou d'un événement assimilé ne génère pas, à lui seul, une obligation découlant de la réglementation internationale de continuer à verser (même à titre provisoire) des prestations.
5.5 On notera enfin que l'art. 114 du règlement no 574/72 règle le versement provisoire de prestations en cas de contestation de la législation applicable ou de l'institution appelée à servir les prestations. Dans ce cas, l'intéressé bénéficie à titre provisoire des prestations prévues par la législation qu'applique l'institution du lieu de résidence. Dès lors, même en admettant que le cas présent requiert une coordination sous l'angle du droit communautaire, une prise en charge préalable incomberait, en application de cette disposition, à l'institution française et non à la première institution à laquelle l'intéressé s'est adressé.
5.6 En conclusion, il n'y a pas de lacune qu'il incomberait au juge de combler. L'argumentation du recourant est sur ce point mal fondée.
6. Le recourant se prévaut de l'art. 78 LPGA en raison d'un acte prétendument illicite de la CNA. Il lui reproche, en particulier, d'être passée totalement à côté de la problématique européenne soulevée par le cas d'espèce. La responsabilité instituée par l'art. 78 LPGA est toutefois subsidiaire en ce sens qu'elle ne peut intervenir que si la prétention invoquée ne peut pas être obtenue par les procédures administrative et judiciaire ordinaires en matière d'assurance sociale ou en l'absence d'une norme spéciale de responsabilité du droit des assurances sociales (ATF 133 V 14 consid. 5 p. 17). La mise en oeuvre de cette responsabilité obéit à des règles de procédure spécifiques. En particulier, la demande doit être présentée à l'autorité compétente qui se prononce ensuite par une décision (art. 78 al. 2 LPGA). Par conséquent, une éventuelle responsabilité de la CNA en vertu de l'art. 78 LPGA excède manifestement l'objet du présent litige et ne saurait donc être examinée ici.
7. 7.1 Le recourant invoque l'interdiction de l'arbitraire (art. 9 Cst.) et le droit à l'égalité de traitement (art. 8 Cst.). Selon lui, le résultat auquel aboutit le jugement attaqué est choquant, en ce sens qu'il conduit le justiciable à devoir assumer seul, en réalité, les frais médicaux relatifs à une atteinte à la santé qu'il a subie, alors qu'il est assuré, qu'il paie des primes et qu'il bénéficie de la protection découlant de la coordination des régimes de sécurité sociale prévue par l'ALCP. Par ailleurs, le jugement attaqué aboutit à traiter de manière dissemblable des situations semblables, selon l'Etat de résidence des personnes assurées contre les accidents auprès de la CNA.
7.2 Comme on l'a vu, le fait qu'il existe une lacune d'assurance résulte du droit d'option exercé par le recourant. Le fait que l'assuré a payé des primes d'assurance-accidents le couvre contre les risques assurés par la LAA. Le recourant ne peut en déduire un droit à des prestations en dehors des risques assurés par cette loi. Par ailleurs, ce n'est pas parce qu'il réside en France que la CNA a refusé ses prestations, mais bien plutôt parce que l'atteinte à la santé ne résulte ni d'un accident ni d'une lésion corporelle assimilée à un accident. Les griefs soulevés ici sont également mal fondés.
8. 8.1 Le recourant se prévaut du droit à la protection de la bonne foi. Il fait valoir à ce propos que la CNA a couvert tous les premiers frais liés à l'événement du 27 octobre 2005, sans faire la moindre réserve. Ce n'est que cinq mois plus tard qu'elle a refusé tout droit aux prestations et qu'elle lui a conseillé de s'annoncer à son assureur-maladie. Pour le recourant, la CNA aurait ainsi créé l'apparence qu'elle se considérait comme définitivement compétente. C'est sur la base de l'attitude de la CNA qu'il s'est fait opérer ensuite, sans qu'un accord pour une hospitalisation à l'étranger n'ait été requis auprès de son assurance-maladie française. Il insiste sur le fait que la prise en charge par cette assurance était soumise à une «entente préalable». Dans ce contexte, le recourant se plaint de ne pas avoir été suffisamment renseigné par l'intimée (art. 27 LPGA).
8.2 Les premiers juges ont écarté ce grief dans un bref considérant. Ils ont retenu que la CNA n'avait jamais garanti formellement la prise en charge des conséquences de l'événement du 27 octobre 2005 et, en particulier, n'avait délivré aucune garantie de paiement à l'Hôpital X._. Par ailleurs, selon eux, il n'appartenait pas à la CNA d'informer l'assuré du comportement à adopter dans un tel cas. Les médecins traitants de l'intéressé assumaient bien plutôt, à l'égard de leur patient, un devoir contractuel d'information minimal en matière économique. C'est à eux qu'il incombait d'attirer l'attention de l'assuré sur le défaut de garantie de paiement, raison pour laquelle d'ailleurs celui-ci devait éprouver des doutes en ce qui concerne la prise en charge de l'intervention et de ses suites.
8.3 Le devoir de conseil de l'assureur social au sens de l'art. 27 al. 2 LPGA comprend l'obligation d'attirer l'attention de la personne intéressée sur le fait que son comportement pourrait mettre en péril la réalisation de l'une des conditions du droit aux prestations (ATF 131 V 472 consid. 4.3 p. 480). Les conseils ou renseignements portent sur les faits que la personne qui a besoin de conseils doit connaître pour pouvoir correctement user de ses droits et obligations dans une situation concrète face à l'assureur (cf. GEBHARD EUGSTER, ATSG und Krankenversicherung: Streifzug durch Art. 1-55 ATSG, RSAS 2003 p. 226). Le devoir de conseils s'étend non seulement aux circonstances de faits déterminantes, mais également aux circonstances de nature juridique (arrêt K 7/06 du 12 janvier 2007 consid. 3.3, in SVR 2007 KV no 14 p. 53 et la référence). Son contenu dépend entièrement de la situation concrète dans laquelle se trouve l'assuré, telle qu'elle est reconnaissable pour l'administration (ULRICH MEYER, Grundlagen, Begriff und Grenzen der Beratungspflicht der Sozialversicherungsträger nach Art. 27 Abs. 2 ATSG, in : Sozialversicherungsrechtstagung 2006, St-Gall 2006, p. 27 no 35).
8.4 Le défaut de renseignement dans une situation où une obligation de renseigner est prévue par la loi, ou lorsque les circonstances concrètes du cas particulier auraient commandé une information de l'assureur, est assimilé à une déclaration erronée qui peut, sous certaines conditions, obliger l'autorité (en l'espèce l'assureur) à consentir à un administré un avantage auquel il n'aurait pu prétendre, en vertu du principe de la protection de la bonne foi découlant de l'art. 9 Cst. (ATF 131 V 472 consid. 5 p. 480). D'après la jurisprudence, un renseignement ou une décision erronés de l'administration peuvent obliger celle-ci à consentir à un administré un avantage contraire à la réglementation en vigueur, à condition que (a) l'autorité soit intervenue dans une situation concrète à l'égard de personnes déterminées, (b) qu'elle ait agi ou soit censée avoir agi dans les limites de ses compétences et (c) que l'administré n'ait pas pu se rendre compte immédiatement de l'inexactitude du renseignement obtenu. Il faut encore qu'il se soit fondé sur les assurances ou le comportement dont il se prévaut pour (d) prendre des dispositions auxquelles il ne saurait renoncer sans subir de préjudice, et (e) que la réglementation n'ait pas changé depuis le moment où l'assurance a été donnée (ATF 131 II 627 consid. 6.1 p. 636 s. et les références citées). Ces principes s'appliquent par analogie au défaut de renseignement, la condition (c) devant toutefois être formulée de la façon suivante: que l'administré n'ait pas eu connaissance du contenu du renseignement omis ou que ce contenu était tellement évident qu'il n'avait pas à s'attendre à une autre information (ATF 131 V 472 consid. 5 p. 480).
8.5 En l'espèce, on ne saurait sans plus, comme l'ont fait les premiers juges, rejeter sur ce point le grief soulevé par le recourant. En effet, il n'est pas d'emblée exclu qu'une absence de renseignement de la part de la CNA ait amené le recourant à renoncer à s'adresser en temps utile à son assureur en France, ce qui aurait pu entraîner la perte de ses droits à l'égard de ce dernier. Ainsi, lors de l'entretien du 21 mars 2006, le recourant a informé le représentant de la CNA du fait qu'il subirait une hospitalisation le 28 mars suivant à l'Hôpital X._. Le procès-verbal de cet entretien ne fait pas état de réserves à ce sujet quant à une éventuelle prise en charge. Si, à cette occasion, le recourant avait été informé que la prise en charge d'un traitement était encore à l'examen, il aurait peut-être reporté l'intervention dans l'attente d'obtenir un accord de prise en charge par son assureur-maladie. A priori, il n'est pas exclu que le recourant puisse se prévaloir, au moins pour les frais de cette hospitalisation, du droit à la protection de la bonne foi. Le jugement attaqué ne contient pas de constatations de fait qui permettraient, à ce stade, de trancher la question. On ignore si la CNA a formulé, à un moment ou à un autre, des réserves sur la prise en charge définitive du cas avant sa décision de refus. Des vérifications s'imposeraient en outre sur le motif invoqué par l'assureur privé pour refuser une prise en charge a posteriori du cas et tiré de l'absence d'une «entente préalable ». Il conviendrait en particulier d'examiner à ce propos le contrat d'assurance conclu par le recourant, ainsi que les conditions générales d'assurance auxquelles ce contrat se réfère. Par ailleurs, il paraît pour le moins singulier, à première vue tout au moins, que l'assuré ait pu se faire opérer à l'Hôpital X._ sans que ce dernier fût en possession d'une garantie de paiement, soit de la CNA, soit de l'assureur privé. Sur ces divers points, un complément d'instruction apparaît donc nécessaire. Il convient donc de renvoyer la cause à l'autorité précédente pour qu'elle établisse les faits pertinents et statue à nouveau sur la question du droit à la protection de la bonne foi de l'assuré. Dans cette mesure, le recours doit être admis.
9. Indépendamment de ce qui précède, il appartiendra aux premiers juges d'examiner la question de la restitution des prestations prononcée par la CNA. Ce point n'a pas été abordé dans le jugement attaqué. On rappellera ici que l'assureur-accidents a la possibilité de mettre fin avec effet ex nunc et pro futuro à son obligation de prester, qu'il avait initialement reconnue, en prenant en charge les frais de traitement, sans devoir se fonder sur un motif de révocation (reconsidération ou révision procédurale), c'est-à-dire liquider le cas en invoquant le fait qu'aucun événement assuré - selon une appréciation correcte de la situation - n'est jamais survenu. En revanche, la restitution doit, dans une telle hypothèse, s'apprécier selon les règles qui président à la révocation des actes administratifs (ATF 130 V 380).
10. Les conclusions du recours ne sont que partiellement admises. Il se justifie de mettre les frais judiciaires pour deux tiers à la charge du recourant et pour un tiers à la charge de l'intimée (art. 66 al. 1 LTF). Le recourant a droit, en outre, à une indemnité de dépens réduite (art. 68 al. 1 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours constitutionnel subsidiaire est irrecevable.
2. Le recours en matière de droit public est partiellement admis.
3. Le jugement attaqué est annulé et la cause renvoyée à la Cour des assurances sociales du Tribunal cantonal du canton de Vaud pour instruction complémentaire et nouvelle décision au sens des motifs.
4. Les frais judiciaires, arrêtés à 750 fr., sont mis pour 500 fr. à la charge du recourant et pour 250 fr. à la charge de l'intimée.
5. L'intimée versera au recourant une indemnité de dépens de 1000 fr. à titre de dépens pour l'instance fédérale.
6. Le présent arrêt est communiqué aux parties, à la Cour des assurances sociales du Tribunal cantonal du canton de Vaud, à l'Office fédéral des assurances sociales et à l'Office fédéral de la santé publique.
Lucerne, le 7 septembre 2009
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Beauverd