Faits:
A. A._, ressortissant du Kosovo, né en 1964, est père de deux filles et d'un fils, nés respectivement en 1983, 1985 et 1986. Ces trois enfants sont issus d'un premier mariage du prénommé avec une compatriote, mariage qui a été dissous le 30 septembre 1991. Les trois demandes d'asile qu'il avait déposées en Suisse en 1990, 1992 et 1995, ont toutes été rejetées. A._ a bénéficié ensuite du report, au 31 juillet 1996, du délai de départ accordé aux requérants kosovars déboutés. Remarié à une ressortissante suisse, le 20 mars 1996, il a obtenu une autorisation de séjour pour regroupement familial. Au mois d'août 1998, il a également pu obtenir des visas d'entrée pour ses trois enfants qui sont venus le rejoindre au mois de novembre suivant; ces derniers ont été mis au bénéfice d'une autorisation de séjour pour regroupement familial en mai 1999.
B. Par décision du 9 juillet 2001, le Service cantonal des étrangers, devenu Service des migrations, a rejeté la demande de permis d'établissement ou de prolongation d'autorisation de séjour formée par A._, au motif que l'intéressé invoquait abusivement son mariage pour rester en Suisse et que son comportement général dénotait au surplus une absence d'intégration. Selon cette décision, le sort des enfants devait suivre celui de leur père.
Le Département de l'économie du canton de Neuchâtel (en abrégé: le Département), par décision du 21 mai 2002, puis le Tribunal administratif du canton de Neuchâtel, par arrêt du 2 décembre 2004, ont confirmé le refus d'accorder une autorisation d'établissement à A._ et de prolonger son autorisation de séjour. En revanche, le Tribunal administratif a partiellement admis le recours, en ce sens que la situation des enfants, devenus majeurs, devait faire l'objet d'un examen séparé de celui de leur père.
Par arrêt du 6 mai 2005 (2A_39/2005), le Tribunal fédéral a rejeté le recours déposé par A._ contre l'arrêt cantonal.
C. Le 6 avril 2006, A._ a présenté une demande de reconsidération de la décision du 9 juillet 2001, que le Service des migrations a déclarée irrecevable, par décision du 29 mai 2006. Le Département a ensuite rejeté le recours contre cette décision, le 13 novembre 2006, en retenant en substance qu'une demande de révision ne pouvait être formée qu'à l'encontre de l'arrêt du Tribunal fédéral du 6 mai 2005.
Le Tribunal administratif a aussi rejeté le recours déposé par A._, par arrêt du 26 janvier 2010. Il a toutefois retenu que des modifications en fait ou en droit, survenues après le jugement final, ne constituaient pas un motif de révision de ce jugement, mais pouvaient justifier une reconsidération de la décision administrative de première instance, de sorte qu'il y avait lieu d'entrer en matière sur la demande de réexamen. Au fond, cette demande devait être rejetée, car les documents produits par le recourant n'étaient pas déterminants et les faits allégués pas nouveaux.
D. A._ forme auprès du Tribunal fédéral un recours en matière de droit public, subsidiairement, un recours constitutionnel subsidiaire et conclut, avec suite de frais et dépens, à l'annulation de l'arrêt du Tribunal administratif du 26 janvier 2010 et au renvoi du dossier à l'autorité inférieure pour nouvelle décision au sens des considérants.
Le Tribunal administratif conclut au rejet du recours, en se référant aux motifs de son arrêt. Le Département de l'économie et le Service des migrations n'ont pas formulé d'observations et concluent au rejet du recours, dans la mesure où il est recevable. L'Office fédéral des migrations propose de rejeter le recours.

Considérant en droit:
1. Le litige porte sur une demande de reconsidération, traitée comme un réexamen, tendant à l'octroi d'une autorisation d'établissement ou à la prolongation d'une autorisation de séjour, que le recourant a déposée le 6 avril 2006, soit avant l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20). Le cas demeure donc régi par l'ancien droit (cf. art. 126 al. 1 LEtr), à savoir la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RO 1 113). Le fait que la juridiction cantonale n'a statué qu'après l'entrée en vigueur de la LEtr n'y change rien (cf. arrêt 2C_745/2008 du 24 février 2009 consid. 1.2).
Le recourant ayant déposé, dans un seul et même acte (<ref-law>), un recours en matière de droit public et un recours de droit constitutionnel subsidiaire, il y a lieu d'examiner au préalable si cette première voie de droit est ouverte (cf. <ref-law>).
2. 2.1 Aux termes de 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.
Il est en l'espèce constant que le recourant ne peut plus se prévaloir de l'art. 7 al. 1 LSEE pour obtenir une autorisation d'établissement, soit de la durée de son mariage avec une ressortissante suisse, le Tribunal fédéral ayant définitivement constaté l'existence d'un abus de droit sur ce point (arrêt 2A.39/2005 du 6 mai 2005, consid. 3).
Le recourant invoque ainsi le droit au respect de sa vie privée et familiale au sens de l'art. 8 § 1 CEDH qui, comme l'art. 13 al. 1 Cst., permet de s'opposer à une éventuelle séparation, à condition que la relation entre l'étranger et une personne de sa famille ayant le droit de résider durablement en Suisse soit étroite et effective (<ref-ruling> consid. 1.3.1 p. 145; <ref-ruling> consid. 3.1 p. 285 et les arrêts cités). Toutefois, les relations visées par l'art. 8 CEDH sont avant tout celles qui existent entre époux, ainsi que les relations entre parents et enfants mineurs vivant en ménage commun (<ref-ruling> consid. 1d/aap. 65). S'agissant d'autres relations entre proches parents, la protection de l'art. 8 CEDH suppose que l'étranger se trouve dans un état de dépendance particulier à l'égard du parent ayant le droit de résider en Suisse. Tel est le cas lorsqu'il a besoin d'une attention et de soins que seuls des proches parents sont en mesure de prodiguer en raison, par exemple, d'un handicap physique ou mental, ou encore d'une maladie grave (arrêt 2C_508/2009 du 20 mai 1010, consid. 2.2). En l'espèce, ce sont les enfants du recourant, tous majeurs, qui ont le droit de séjourner en Suisse. Or, le recourant, qui soutient même financièrement ses deux cadets, ne se trouve pas dans un rapport de dépendance particulier vis-à-vis de ses enfants au sens de la jurisprudence précitée. Il n'a donc en principe pas un droit à une autorisation de séjour ou d'établissement sur la base de l'art. 8 CEDH.
2.2 Il s'ensuit qu'en vertu de l'art. 83 let. c ch. 2 LTF, le présent recours n'est pas recevable comme recours en matière de droit public Il y a lieu dès lors d'examiner s'il peut être traité comme recours de droit constitutionnel subsidiaire.
3. 3.1 Le recours constitutionnel subsidiaire ne peut être formé que pour violation des droits constitutionnels (<ref-law>), grief que le recourant doit invoquer et motiver suffisamment sous peine d'irrecevabilité (<ref-law> applicable par renvoi de l'<ref-law>). En outre, le recourant doit avoir un intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>). Un recourant n'a qualité pour former un recours constitutionnel subsidiaire que si les dispositions légales dont il dénonce l'application arbitraire lui accordent un droit ou servent à protéger ses intérêts prétendument lésés (cf. <ref-ruling> consid. 6.1 p. 197 s. et 6.3 p. 200). Selon la jurisprudence en effet, l'interdiction générale de l'arbitraire découlant de l'art. 9 Cst. ne confère pas, à elle seule, une position juridique protégée au sens de l'<ref-law> (cf. <ref-ruling> consid. 4 à 6 p. 191 ss).
3.2 Le recours constitutionnel subsidiaire permet toutefois au recourant qui, comme en l'espèce, n'a pas la qualité pour agir au fond de se plaindre de la violation de ses droits de partie équivalant à un déni de justice formel, pour autant que, par ce biais, il n'invoque pas, même indirectement, des moyens ne pouvant être séparés du fond (cf. <ref-ruling> consid. 6.2 p. 198 s.; voir aussi <ref-ruling> consid. 1.4 p. 222). A ce titre, le présent recours n'est donc pas recevable comme recours constitutionnel subsidiaire, en tant que le recourant se plaint d'arbitraire dans la constatation des faits à laquelle a procédé le Tribunal administratif.
Toutefois, dans le cadre de ce recours, le recourant invoque aussi une violation du droit d'être entendu au sens de l'art. 29 al. 2 Cst., ainsi qu'un déni de justice formel. Dans cette limite, son recours est recevable s'agissant de griefs procéduraux qui ne concernent pas le fond du litige.
3.3 Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend notamment pour le justiciable le droit de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, d'obtenir l'administration des preuves pertinentes et valablement offertes, de participer à l'administration des preuves essentielles et de se déterminer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.1 p. 277 et la jurisprudence citée).
3.4 En l'espèce, le Service des migrations n'est pas entré en matière sur la demande de reconsidération présentée le 6 avril 2006 par le recourant au motif que celle-ci devait être adressée au Tribunal fédéral, dont l'arrêt du 6 mai 2005 avait remplacé sa décision du 9 juillet 2001. Le Département a rejeté le recours de l'intéressé, le 13 novembre 2006, en confirmant ce point de vue.
Dans l'arrêt attaqué, le Tribunal administratif a admis à juste titre que des modifications en fait ou en droit, survenues après le jugement final, ne constituaient pas un motif, de révision de ce jugement, mais qu'elles pouvaient justifier un réexamen de la décision administrative primaire. Il en a déduit que les conditions pour revoir la décision du 9 juillet 2001 par l'autorité de première instance étaient probablement réunies et que le Service des migrations aurait dû entrer en matière au sujet des faits invoqués par le recourant, notamment sur les liens affectifs que celui-ci entretient avec ses enfants et les autorisations de séjours accordées aux deux cadets (consid. 3c p. 6). Le Tribunal administratif a cependant rejeté le recours, au motif que ces faits n'étaient pas nouveaux du point de vue d'une procédure de réexamen, car le recourant s'était expressément référé, dans son recours au Tribunal fédéral contre son premier jugement du 2 décembre 2004, à la question du regroupement familial en faveur de ses enfants, à l'autorisation de séjour accordée à sa fille aînée et à la possibilité pour ses deux cadets d'obtenir une telle autorisation. Il a ainsi considéré que le Tribunal fédéral s'était implicitement prononcé sur l'influence que pouvaient avoir les relations du recourant avec ses enfants par rapport à l'octroi d'une autorisation de séjour ou d'établissement à ce dernier, de sorte que ces éléments ne pouvaient être soulevés une nouvelle fois dans la demande de réexamen.
Or, dans son arrêt du 6 mai 2005 (2A.39/2005), le Tribunal fédéral a uniquement examiné si le recourant pouvait obtenir une autorisation d'établissement sur la base de l'art. 7 al. 1 LSEE, en raison de la durée de son mariage avec une ressortissante suisse. Partant, il ne s'est fondé que sur le comportement du recourant par rapport à son ex-épouse pour conclure qu'il y avait abus de droit à se prévaloir d'un mariage qui n'existait plus que formellement avant l'échéance du délai de cinq ans. Il ne s'est nullement penché sur le cas des enfants du recourant, déjà majeurs à l'époque, en retenant qu'il était lié par les faits constatés par la juridiction cantonale (<ref-law>). Il n'y avait ainsi pas lieu d'entrer en matière sur les faits allégués par le recourant au sujet de ses enfants, car ils étaient nouveaux. Le Tribunal fédéral a seulement ajouté que les pièces nouvelles que le recourant produisait à l'égard de ses filles seraient de toute manière dénuées de pertinence, dans la mesure où leur cas avait été disjoint de sa propre cause (arrêt du 6 mai 2005, consid. 2 p. 6). Dans ces conditions, le Tribunal administratif ne pouvait considérer que le Tribunal fédéral s'était implicitement prononcé sur la situation du recourant par rapport à celle de ses enfants et en conclure que les faits allégués par le recourant dans sa demande de réexamen n'étaient pas nouveaux.
3.5 La substitution de motifs à laquelle la juridiction cantonale a procédé pour rejeter le recours contre la décision du Département est donc erronée et constitue un déni de justice formel, dans le sens où les autorités ont indûment refusé de se prononcer sur la demande de réexamen du recourant (cf. <ref-ruling> consid. 3b p. 164, confirmé notamment in arrêt 2C_780/2008 du 15 juin 2009, consid. 2.2). Ce faisant, la juridiction cantonale a empêché que la situation du recourant par rapport à ses enfants soit réexaminée par le Service des migrations au regard du temps qui s'est écoulé depuis sa décision du 9 juillet 2001, dans laquelle il avait d'ailleurs retenu que le sort des enfants devait suivre celui de leur père. Même si le recourant n'a pas un droit à une autorisation de séjour sur la base de l'art. 8 CEDH, il ne paraît en effet pas impossible qu'il obtienne une autorisation en application de l'art. 30 LEtr (anciennement art. 13 let. f de l'ordonnance sur le séjour et l'établissement des étrangers du 6 octobre 1986: OLE; RO 1986 p. 1791 et les modifications ultérieures) en raison des liens familiaux étroits qu'il entretient avec ses enfants et de la durée de son séjour en Suisse.
4. Au vu de ce qui précède, le recours, irrecevable comme recours en matière de droit public, doit être admis dans la mesure où il est recevable comme recours de droit constitutionnel subsidiaire et l'arrêt attaqué annulé. En application de l'<ref-law>, applicable en vertu de l'<ref-law>, la cause sera renvoyée à l'autorité cantonale de première instance pour qu'elle entre en matière sur la demande de réexamen de sa décision du 9 juillet 2001.
Le présent arrêt sera rendu sans frais (<ref-law>). En revanche, le canton de Neuchâtel versera au mandataire du recourant une indemnité à titre de dépens pour la procédure devant le Tribunal fédéral (<ref-law>). Il y a lieu également de renvoyer la cause au Tribunal administratif pour qu'il fixe à nouveau les frais et dépens de la procédure cantonale (art. 67 et 68 al. 5 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière de droit public est irrecevable.
2. Le recours constitutionnel subsidiaire est admis dans la mesure où il est recevable et l'arrêt attaqué annulé.
3. La cause est renvoyée au Service des migrations pour nouvelle décision au fond dans le sens des considérants.
4. Il n'est pas perçu de frais judiciaires.
5. Le canton de Neuchâtel versera au mandataire du recourant une indemnité de 1'500 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
6. La cause est renvoyée au Tribunal administratif pour nouvelle décision sur la question des frais et dépens de la procédure cantonale.
7. Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations, au Département de l'économie et à la Cour de droit public du Tribunal administratif du canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 27 juillet 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président La Greffière
Zünd Rochat