Faits:
A. Le 19 octobre 2006, Stéphane Clavien a déposé auprès de la Commune de Miège en Valais une demande d'autorisation de séjour CEE/AELE de courte durée en vue d'exercer une activité lucrative en faveur de Claude Vorilhon. Statuant le 14 février 2007, le Service de l'état civil et des étrangers a refusé de délivrer l'autorisation de séjour et signifié à Claude Vorilhon qu'il était tenu de quitter la Suisse à l'issue de son séjour touristique.
Par décision du 19 septembre 2007, le Conseil d'Etat du canton du Valais a rejeté les recours séparés, mais identiques, de Stéphane Clavien et de Claude Vorilhon contre la décision du 14 février 2007.
Par arrêt du 17 avril 2008, le Tribunal cantonal a rejeté le recours déposé contre la décision du 19 septembre 2007.
Par arrêt du 15 septembre 2008, le Tribunal fédéral a rejeté dans la mesure où il était recevable le recours déposé par Claude Vorilhon et Stéphane Clavien contre l'arrêt du 17 avril 2008 (2C_396 /2008).
B. Le 29 juillet 2009, Claude Vorilhon et Stéphane Clavien ont adressé au Tribunal cantonal du canton du Valais une demande en révision de l'arrêt rendu le 17 avril 2008 fondée sur l'art. 62 de la loi valaisanne du 6 octobre 1976 sur la procédure et la juridiction administrative (LJPA; RSVS 172.6). La demande était fondée sur la découverte, le 1er mai 2009, d'une lettre adressée le 14 septembre 2007 par Françoise Gianadda, cheffe du Service de l'état civil et des étrangers, à l'Association suisse pour la défense de la famille et de l'individu, dans laquelle était refusée la communication de la décision du 14 février 2007, sollicitée par courrier du 29 août 2007. Dans sa lettre du 14 septembre, F. Gianadda écrivait en outre soutenir "tous les faits ayant trait à la lutte contre les sectes et leurs dérives" et formulait les "meilleurs voeux de réussite à Mme [...] dans le cadre de son procès qui l'oppose à Raël". La production de la lettre du 29 août 2007 était requise à titre de moyen de preuve. La demande se fondait aussi sur une interview publiée le 19 [recte: le 17] mai 2009 par le "Matin Dimanche", au cours de laquelle F. Gianadda aurait tenu des "propos ouvertement hostiles à l'établissement de Claude Vorilhon". Ces éléments auraient, selon les demandeurs, justifié la récusation de F. Gianadda en application de l'art. 10 al. 1 let. e LJPA.
C. Par arrêt du 30 octobre 2009, le Tribunal cantonal a déclaré irrecevable la demande en révision du 29 juillet 2009. La demande se fondait à tort sur l'art. 62 LJPA. Seul l'art. 236 du code de procédure civile du 24 mars 1998 (CPC/VS; RSVS 270.1) trouvait application. La publication de l'interview dans le "Matin Dimanche" était un fait postérieur à l'arrêt rendu le 17 avril 2008; elle ne constituait pas un motif de révision, contrairement à la lettre du 14 septembre 2007. Ce courrier était toutefois postérieur à la décision rendue le 14 février 2007 par le Service de l'état civil et des étrangers dirigé par F. Gianadda. Il ne prouvait pas que l'opinion qui y figurait était l'expression d'un préjugé antérieur aux constatations de contrariété à l'ordre public résultant de la procédure administrative. Elle pouvait aussi en être la simple conséquence. La production de cette lettre lors de la procédure principale de recours devant le Tribunal cantonal n'aurait par conséquent pas conduit à l'annulation de la décision du Conseil d'Etat du 19 septembre 2007 pour défaut de prise en compte d'un vice de forme de la décision rendue le 14 février 2007 par le Service de l'état civil et des étrangers. La production de la lettre du 29 août 2007 adressée au Service cantonal de l'état civil et des étrangers n'éclairait en rien une éventuelle prévention de F. Gianadda. Elle était par conséquent refusée.
D. Agissant par la voie du recours en matière de droit public et par la voie du recours constitutionnel subsidiaire, Claude Vorilhon et Stéphane Clavien demandent au Tribunal fédéral de réformer l'arrêt rendu le 30 octobre 2009 en ce sens que la demande de révision déposée le 29 juillet 2009 par Claude Vorilhon et Stéphane Clavien est admise, l'arrêt rendu le 17 avril 2008 ainsi que les décisions rendues le 19 décembre 2007 par le Conseil d'Etat et le 14 février 2007 par le Service de l'état civil et des étrangers sont annulés et la cause renvoyée au Service de l'état civil et des étrangers pour nouvelle décision. Ils invoquent nouvellement la violation des art. 30 al. 1 Cst., 6 § 1 CEDH ainsi que 14 § 1 Pacte ONU II.
Le Service de la population et des migrations (anciennement: de l'état civil et des étrangers) ainsi que le Tribunal cantonal ont renoncé à déposer des observations. Le Conseil d'Etat conclut au rejet du recours dans la mesure où il est recevable. L'Office fédéral des migrations conclut au rejet du recours.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 96 et la jurisprudence citée). Il examine d'office aussi les conditions de recevabilité du recours devant l'instance précédente et si c'est à bon droit que celle-ci est entrée en matière (<ref-ruling> consid. 3 p. 25).
2. L'arrêt du Tribunal cantonal fait l'objet d'un recours en matière de droit public et d'un recours constitutionnel subsidiaire. Le second étant irrecevable en cas de recevabilité du premier (<ref-law>), il convient d'examiner en priorité si la voie du recours en matière de droit public est ouverte.
Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit. Le recours en matière de droit public est recevable en l'espèce du moment que la demande en révision dirigée contre l'arrêt rendu le 17 avril 2008 peut placer les recourants dans la situation qui était la leur lorsqu'ils avaient déposé le 23 mai 2008 leur premier recours auprès du Tribunal fédéral, dont la recevabilité a déjà été admise sous l'angle de l'art. 83 let. c ch. 2 LTF (arrêt 2C_396/2008 du 15 septembre 2008, consid. 2.2). Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (art. 42 et 106 al. 2 LTF) par les destinataires de la décision attaquée qui ont un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), le recours est en principe recevable en vertu des <ref-law>.
Il s'ensuit que le recours constitutionnel subsidiaire, dont est simultanément saisi le Tribunal fédéral, est irrecevable (cf. <ref-law>).
3. La procédure (principale) concernant la demande d'autorisation de séjour déposée par les recourants a fait l'objet d'un arrêt rendu le 17 avril 2008 par le Tribunal cantonal et d'un arrêt du Tribunal fédéral du 15 septembre 2008, qui a rejeté dans la mesure où il était recevable le recours en matière de droit public dirigé contre l'arrêt cantonal. Les recourants ont déposé leur demande en révision fondée sur des faits et moyens de preuve nouveaux auprès du Tribunal cantonal.
3.1 Aux termes de l'<ref-law>, la révision peut être demandée dans les affaires de droit public si le requérant découvre après coup des faits pertinents ou des moyens de preuve concluants qu'il n'avait pas pu invoquer dans la procédure précédente, à l'exclusion des faits ou moyens de preuve postérieurs à l'arrêt. Les lois de procédure cantonales ouvrent en principe aussi la voie de la révision en pareille hypothèse. Ainsi, dans l'arrêt attaqué, le Tribunal cantonal a examiné la demande de révision dont il était saisi en application de l'<ref-law>/VS, selon lequel peut demander la révision celui qui, après le prononcé d'un jugement définitif, découvre des faits ou moyens de preuve nouveaux qui auraient influencé le jugement en sa faveur et qui ne pouvaient être invoqués à temps en usant de toute l'attention requise. Selon un principe général toutefois, la demande en révision, sur le fond, doit être formée devant l'autorité qui a statué sur le fond en dernière instance (<ref-ruling> consid. 2.2 p. 48; <ref-ruling> consid. 2 p. 367 s. et les références citées).
3.1.1 La jurisprudence a eu l'occasion de préciser à cet égard, en relation avec les voies de droit de l'ancienne organisation judiciaire fédérale (OJ), que, lorsque le Tribunal fédéral rejetait ou déclarait irrecevable le recours de droit public, ou déclarait irrecevable le recours en réforme, son arrêt ne se substituait pas à la décision cantonale attaquée; celle-ci demeurait en force et était sujette à révision cantonale pour les motifs qui affectaient l'état de fait qu'elle constatait. Les faits pertinents et moyens de preuve concluants qui existaient déjà au moment où, dans la procédure (cantonale) principale, des allégations de fait et offres de preuve étaient encore recevables, mais qui n'étaient pas connus du requérant malgré toute sa diligence et n'ont été découverts par lui que postérieurement à l'arrêt du Tribunal fédéral, pouvaient donc faire l'objet d'une procédure de révision cantonale devant la dernière juridiction cantonale saisie de la cause au fond aux conditions du droit cantonal (<ref-ruling> consid. 2.2 p. 670 s.; <ref-ruling> consid. 2.2 et 2.3 p. 47/48, avec les références citées). En revanche, lorsque, statuant sur la base des faits constatés dans la décision cantonale, le Tribunal fédéral admettait ou rejetait le recours en réforme, son arrêt se substituait à la décision (cantonale) entreprise et constituait la seule décision en force susceptible d'être révisée pour les motifs actuellement énumérés aux art. 121 et 123 LTF (<ref-ruling> consid. 2.2 p. 670 s.).
3.1.2 Le recours en matière de droit public étant une voie de droit ordinaire de nature réformatoire (<ref-law>), son admission ou son rejet sur la base des faits constatés dans la décision attaquée conduit à ce que l'arrêt du Tribunal fédéral se substitue à la décision attaquée. Dans cette hypothèse, la demande en révision doit être formée devant le Tribunal fédéral dont l'arrêt constitue alors la seule décision en force (cf. <ref-law>) susceptible d'être révisée pour les motifs énumérés aux art. 121 et 123 LTF (cf. YVES DONZALLAZ, Loi sur le Tribunal fédéral, Berne 2008, n° 4645 p. 1671; Nicolas von Werdt, Bundesgerichtsgesetz, Berne 2007, n° 13 ad <ref-law>). En revanche, la demande en révision doit être formée devant l'instance précédente lorsque le recours en matière de droit public est déclaré irrecevable ou lorsque le motif de la demande en révision porte sur des aspects qui n'étaient plus litigieux en procédure principale devant le Tribunal fédéral (arrêt 2F_2/2009 du 23 septembre 2009, consid. 2.2 et 2.3).
3.2 En l'espèce, le recours en matière de droit public déposé contre l'arrêt rendu le 17 avril 2008 par le Tribunal cantonal a été rejeté dans la mesure où il était recevable par arrêt du Tribunal fédéral du 15 septembre 2008. Ce dernier a statué sur le fond, de sorte que les recourants n'étaient pas en droit de former une demande en révision auprès du Tribunal cantonal. Il convient par conséquent de confirmer, par substitution de motifs, l'irrecevabilité prononcée par le Tribunal cantonal dans son arrêt du 30 octobre 2009.
4. Sur le fond, le recours devait de toute manière être rejeté.
4.1 La récusation d'une autorité autre que judiciaire, comme en l'espèce de F. Gianadda en tant que cheffe du Service de l'état civil et des étrangers du canton du Valais, est réglée par le droit de procédure applicable et l'art. 29 al. 1 Cst. Les garanties de procédure judiciaire des art. 30, 6 § 1CEDH et 14 § 1 Pacte ONU II, invoquées par les recourants, ne trouvent pas d'application en pareil cas (cf. arrêts 8C_425/2009 du 9 octobre 2009 consid. 3; 1P.489/2001 du 4 décembre 2001 consid. 2c; ainsi que sous l'empire de l'ancienne Cst.: <ref-ruling> consid. 3b p. 123, 209 consid. 8a p. 217 s. avec références). Pour le surplus, le Tribunal fédéral ne peut examiner d'office (cf. <ref-law>) la violation de l'art. 29 Cst. puisqu'elle n'a fait l'objet d'aucun grief de la part des recourants.
4.2 Enfin, les recourants considèrent en vain que l'interprétation de l'<ref-law>/VS par le Tribunal cantonal est arbitraire en ce sens qu'elle prive la partie qui ne peut pas découvrir les preuves de la partialité de l'autorité ou l'existence d'un motif de récusation avant la décision d'en obtenir la révision. En effet, ils perdent de vue qu'ils ne détiennent pas la preuve de la partialité qu'ils dénoncent. Comme l'a jugé le Tribunal cantonal, la lettre du 14 septembre 2007 ne démontrait pas que F. Gianadda avait une opinion préconçue hostile à l'égard des recourants lorsqu'elle a rendu la décision du 14 février 2007. La succession dans le temps des événements, en d'autres termes, le fait que la décision du 14 février 2007 soit antérieure à la lettre du 14 septembre 2007, permettait, quoi qu'en pensent les recourants, d'en décider ainsi sans procéder à une appréciation arbitraire des preuves (cf. sur cette notion: <ref-ruling> consid. 7.1 p. 398).
5. Les considérants qui précèdent conduisent au rejet du recours en matière de droit public et à l'irrecevabilité du recours constitutionnel subsidiaire.
Succombant, les recourants doivent supporter un émolument judiciaire, solidairement entre eux (art. 65 et 66 LTF). Ils n'ont pas droit à des dépens (<ref-law>).

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 rejeté.
3. Les frais judiciaires, arrêtés à 2'500 fr., sont mis à la charge des recourants solidairement entre eux.
4. Le présent arrêt est communiqué aux parties, au Service de la population et des migrations du canton du Valais, au Conseil d'Etat du canton du Valais, au Tribunal cantonal du canton du Valais, Cour de droit public, et à l'Office fédéral des migrations.
Lausanne, le 26 mai 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Dubey