Faits:
A. X._, ressortissant marocain, est entré en Suisse au bénéfice d'un visa touristique en juin 2002 et une nouvelle fois en août 2002 alors qu'il ne possédait qu'un visa pour les Etats de l'espace Schengen. Le 31 juillet 2003, il a épousé à A._ (GE) une ressortissante suisse et a obtenu une autorisation de séjour par regroupement familial. Le 31 juillet 2003, il s'est constitué un domicile à B._ (NE), tandis que son épouse s'est établie à C._ (NE) le 1er novembre 2003.
B. Sur réquisition du Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) du 16 août 2007, la police cantonale a rendu un rapport le 20 novembre 2007, aux termes duquel les époux avaient choisi de vivre séparément pour sauver leur couple en raison de la pression exercée par les enfants du premier mariage de D._.
Par décision du 28 novembre 2008, le Service des migrations a refusé à X._ la prolongation de son autorisation de séjour et lui a imparti un délai au 15 janvier 2009 pour quitter la Suisse. Le recours interjeté contre cette décision a été rejeté par le Département de l'économie neuchâtelois (ci-après: le Département de l'économie) en date du 5 octobre 2009. Par arrêt du 16 février 2010, la Cour de droit public du Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté le recours formé par X._ contre la décision du 5 octobre 2009.
C. Agissant par la voie du recours en matière de droit public et par celle du recours constitutionnel subsidiaire, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal administratif du 16 février 2010 et de lui accorder le droit à la prolongation de son permis de séjour; subsidiairement, de renvoyer l'affaire à l'autorité compétente pour nouvelle décision au sens des considérants; plus subsidiairement, de renvoyer l'affaire à l'autorité compétente pour instruction complémentaire et nouvelle décision.
Le Service des migrations se réfère aux motifs de l'arrêt du Tribunal administratif et conclut, avec suite de frais, au rejet du recours, en tant qu'il est recevable. Le Tribunal administratif et le Département de l'économie se réfèrent également aux motifs de l'arrêt entrepris et concluent au rejet du recours, s'agissant du Département dans la mesure où le recours est recevable. L'Office fédéral des migrations propose lui aussi le rejet du recours.
D. Par courrier du 6 octobre 2010, le Service des migrations a transmis au Tribunal fédéral, "en complément à" ses précédentes observations, diverses pièces et un courrier reçus de l'épouse de X._ censés notamment établir le mariage de ce dernier au mois de septembre 2010 avec une seconde épouse.

Considérant en droit:
1. 1.1 La loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) est entrée en vigueur le 1er janvier 2008. En vertu de l'art. 126 al. 1 LEtr, les demandes déposées avant cette dernière date sont régies par l'ancien droit. La procédure ayant conduit à la décision de non-renouvellement de l'autorisation de séjour de X._, qui est à l'origine du litige, a débuté en 2007, soit avant l'entrée en vigueur de la LEtr, si bien que la présente cause doit être examinée, à l'exception des questions de procédure (art. 126 al. 2 LEtr), à la lumière de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers [LSEE; RS 1 113] (cf. <ref-ruling> consid. 1.1 p. 122).
1.2 La question de savoir si l'examen du renvoi de Suisse prononcé dans le cadre de la décision du 28 novembre 2008, qui est la conséquence du rejet de la demande de prolongation d'autorisation de séjour (cf. Nicolas Wisard, Les renvois et leur exécution en droit des étrangers et en droit d'asile, Bâle / Genève / Francfort-sur-le-Main 1997, p. 130), est soumis à la LSEE ou à la LEtr peut demeurer ouverte en l'espèce, dès lors que seul le recours de droit constitutionnel subsidiaire permettrait d'examiner ledit renvoi mais que ce recours doit être déclaré irrecevable (cf. consid. 2.3 et 5 ci-dessous).
2. Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 96).
2.1 Le recourant a interjeté, en un seul acte conformément à l'<ref-law>, un recours en matière de droit public et un recours constitutionnel subsidiaire. Le second étant irrecevable en cas de recevabilité du premier (<ref-law>), il convient d'examiner si la voie du recours en matière de droit public est ouverte.
2.2 D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Le recourant est encore marié à une ressortissante suisse. En principe, il dispose donc, en vertu de l'art. 7 al. 1 LSEE, d'un droit (dérivé) à une autorisation de séjour en Suisse pendant toute la durée formelle de son mariage (<ref-ruling> consid. 8.3 p. 129; arrêt 2C_444/2009 du 21 janvier 2010 consid. 2.2). Son recours est dès lors recevable sous cet angle, la question de savoir si le refus de la prolongation de l'autorisation de séjour sollicitée se justifie en raison d'un abus de droit devant être examinée au fond (<ref-ruling> consid. 1b p. 266).
2.3 Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>) - la transmission du dossier au Service des migrations ne concernant que la conséquence pratique de la fixation d'une nouvelle date de renvoi de Suisse -, qui a été rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Le recours a été formé en temps utile (art. 100 al. 1 et 46 al. 1 let. c LTF) et dans les formes prescrites (<ref-law>) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'<ref-law>. Il est en principe recevable comme recours en matière de droit public et, par conséquent, irrecevable comme recours constitutionnel subsidiaire (<ref-law>).
2.4 Le courrier du 6 octobre 2010 et ses annexes que l'intimé a adressés au Tribunal fédéral constituent des moyens nouveaux au sens de l'<ref-law> dont la présentation n'est pas admise à moins de résulter de la décision de l'autorité précédente. Cette exception n'étant pas donnée en l'espèce, ces nova sont irrecevables et ne seront donc pas pris en considération dans le cadre de la présente procédure (cf. arrêts 4A_18/2010 du 15 mars 2010 consid. 2 non publié aux <ref-ruling>; 2C_94/2009 du 16 juin 2009 consid. 2.2).
3. Les autorités cantonales ont refusé de prolonger l'autorisation de séjour du recourant et prononcé son renvoi en retenant en substance que les époux n'ayant jamais vécu ensemble durant leur mariage, le fait pour le recourant de se prévaloir de son mariage constituait un abus de droit. Le recourant le conteste et remet en cause les faits constatés et les preuves appréciées par le Tribunal administratif, en affirmant notamment que sa présence au domicile de son épouse serait constante du fait que s'y trouveraient ses affaires personnelles, que la reprise de la vie commune aurait été tentée à plusieurs reprises et que la police cantonale aurait pu constater, en vérifiant dans la salle de bains au domicile distinct du recourant, la présence d'affaires féminines appartenant à l'épouse de l'intéressé. Quant à ce dernier point, X._ semble se plaindre également d'une violation de son droit d'être entendu.
3.1 Le droit d'être entendu (art. 29 al. 2 Cst.) ne s'oppose pas à ce que l'autorité mette un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 2.1 p. 428, confirmé récemment in: arrêt 2C_51/2010 du 23 août 2010 consid. 2.3). Lorsque, comme en l'espèce, le recourant semble percevoir une violation du premier principe dans le fait que le Tribunal administratif a failli à son devoir d'examiner les faits et de traiter les problèmes pertinents, le grief du droit d'être entendu se confond avec celui de l'arbitraire dans l'appréciation des preuves (cf. <ref-ruling> consid. 5.3 p. 148). Il sera traité au considérant 3.3 ci-après.
3.2 En principe, le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Le recourant ne peut critiquer ceux-ci que s'ils ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.3 p. 62) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), ce qu'il lui appartient d'exposer et de démontrer de manière claire et circonstanciée. La correction du vice soulevé doit en outre être susceptible d'influer sur le sort de la cause (<ref-law>). En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (cf. <ref-ruling> consid. 3 p. 104 s; <ref-ruling> consid. 1.4 p. 254 s; <ref-ruling> consid. 2.1 p. 120).
Selon la jurisprudence, l'arbitraire, prohibé par l'art. 9 Cst., ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral ne s'écarte de la solution retenue en dernière instance cantonale que si elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté ou si elle heurte de manière choquante le sentiment de la justice ou de l'équité. Il ne suffit pas que la motivation de la décision soit insoutenable; encore faut-il qu'elle soit arbitraire dans son résultat (<ref-ruling> consid. 5.4 p. 148; <ref-ruling> consid. 3.1 p. 153).
3.3 En l'espèce, le recourant n'indique pas en quoi l'appréciation des faits et des preuves opérée par le Tribunal administratif serait arbitraire ou conduirait à un résultat choquant. En critiquant les faits constatés, le recourant se contente d'y substituer sa propre version, sans établir que celle figurant dans l'arrêt entrepris serait manifestement inexacte, de sorte que la question de la recevabilité de ce grief se pose. Au demeurant, contrairement à ce que semble vouloir indiquer le recourant, le Tribunal administratif n'a pas commis d'arbitraire en faisant sien le constat du Département de l'économie selon lequel, s'il peut être plausible que des tensions avec les enfants aient initialement nécessité que les époux se constituent des domiciles séparés, l'évolution positive décrite par le recourant aurait pu et dû conduire les époux à tenter de reprendre la vie commune. Il n'est pas non plus choquant qu'à défaut de preuves y relatives, le Tribunal administratif ait retenu: l'absence de toute tentative des époux de vivre sous un même toit; l'absence de nécessité professionnelle dictant une vie séparée, ou encore le défaut d'autres indices (photographies) étayant l'union du couple.
Par ailleurs, et bien qu'il soit certes regrettable que la police cantonale n'ait pas, dans son rapport du 20 novembre 2007, mentionné d'éventuelles recherches qu'elle aurait effectuées dans la salle de bains au domicile du recourant, l'appréciation anticipée des preuves à laquelle a procédé le Tribunal administratif en retenant en substance que le constat d'affaires féminines dans ladite pièce n'aurait pas modifié son appréciation au vu, notamment, de l'existence d'autres indices étayant un abus de droit et du contenu probatoire relatif d'une découverte de ce genre, ne passe pas non plus pour arbitraire et ne viole pas le droit d'être entendu du recourant.
Le grief du recourant tiré de l'établissement et de l'appréciation arbitraire des faits, ainsi que celui tiré de la violation du droit d'être entendu, qui se confond avec le premier grief (cf. supra consid. 3.1), doivent en conséquence être rejetés en tant qu'ils sont recevables. Dans la suite de son raisonnement, le Tribunal fédéral se limitera partant aux faits constatés par le Tribunal administratif.
4. Le recourant reproche au Tribunal administratif d'avoir violé les art. 7 LSEE et 8 CEDH garantissant le respect de la vie privée et familiale, dans la mesure où il a confirmé la décision refusant la prolongation de son autorisation de séjour.
4.1 D'après l'art. 7 LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour (al. 1, 1ère phrase) puis, après un séjour régulier et ininterrompu de cinq ans, à l'autorisation d'établissement (al. 1, 2ème phrase), à moins que le mariage n'ait été contracté dans le but d'éluder les dispositions sur le séjour et l'établissement des étrangers (al. 2). L'art. 8 CEDH consacre le droit au respect de la vie privée et familiale (par. 1), tout en admettant qu'il puisse y avoir une ingérence dans son exercice à certaines conditions (par. 2). Pour pouvoir invoquer la protection familiale découlant de l'art. 8 par. 1 CEDH, l'étranger doit entretenir une relation étroite et effective (<ref-ruling> consid. 5 p. 269; <ref-ruling> consid. 5.3.1 p. 211; arrêt de la CourEDH du 2 août 2001 dans la cause Boultif c. Suisse, Recueil CourEDH 2001-IX par. 48) avec une personne de sa famille ayant le droit de résider durablement en Suisse (cf. <ref-ruling> consid. 1.3.1 p. 145 s).
4.2 Les droits mentionnés par les art. 7 LSEE et 8 CEDH sont accordés sous réserve d'un abus de droit (<ref-law>). Il y a abus de droit notamment lorsqu'une institution juridique est utilisée à l'encontre de son but pour réaliser des intérêts que cette institution juridique ne veut pas protéger (<ref-ruling> consid. 4 p. 101/102; <ref-ruling> consid. 5a p. 56; <ref-ruling> consid. 4 p. 103; arrêt 2C_289/2008 du 30 septembre 2008 consid. 2.2). Tel est le cas notamment lorsque le conjoint étranger invoque un mariage n'existant plus que formellement dans le seul but d'obtenir une autorisation de police des étrangers, car cet objectif n'est pas protégé par l'art. 7 al. 1 LSEE. Comme indice pour un abus de droit, le Tribunal fédéral a eu l'occasion de considérer le lien conjugal comme vidé de son contenu près de deux ans après la fin de la vie commune (<ref-ruling> consid. 10.3 et 10.4 p. 135 ss). Cependant, l'on ne saurait déduire du simple fait que les époux ne vivent pas (ou plus) ensemble l'existence d'un abus de droit, le législateur ayant volontairement renoncé, à l'art. 7 al. 1 LSEE, à faire dépendre le droit à une autorisation de séjour de la vie commune (<ref-ruling> consid. 3 p. 149 ss, confirmé récemment in: arrêt 2C_278/2008 du 18 juin 2008 consid. 4.1). En tout état, l'existence d'un éventuel abus de droit doit être appréciée dans chaque cas particulier et avec retenue, seul l'abus manifeste pouvant être pris en considération (<ref-ruling> consid. 4.2 p. 267; arrêt 2C_167/2010 du 3 août 2010 consid. 7.2).
4.3 En l'occurrence, le recourant était illégalement entré en Suisse au mois d'août 2002 et avait peu après déposé un dossier en vue de son mariage, célébré à A._ (GE) le 31 juillet 2003. Depuis lors et jusqu'au moment du prononcé de l'arrêt attaqué le 16 février 2010, il n'a jamais fait ménage commun avec son épouse. La vie séparée du couple ne se justifie de plus ni au regard d'une nécessité professionnelle ni par rapport aux tensions rencontrées avec les enfants du premier lit de l'épouse du recourant, qui se sont estompées entre-temps. Le recourant ne fait du reste valoir aucun motif concret propre à justifier cette vie séparée. Aussi, le couple n'a-t-il, depuis près de sept années, jamais entrepris de tentative de mener une vie conjugale commune. D'ailleurs, l'on cherche en vain des éléments laissant apparaître que, malgré l'absence de vie commune des époux au quotidien, ceux-ci entretiendraient néanmoins entre eux des relations d'une intensité suffisante pour fonder une communauté conjugale méritant de bénéficier de la protection prévue à l'art. 7 al. 1 LSEE ou à l'art. 8 CEDH.
Partant, c'est à juste titre que le Tribunal administratif a retenu que le fait pour le recourant de se prévaloir de son mariage était constitutif d'un abus de droit. Il n'a donc pas violé les art. 7 LSEE et art. 8 CEDH en refusant d'accorder une prolongation de son autorisation de séjour en Suisse au recourant.
5. 5.1 Le recourant reproche aussi au Tribunal administratif d'avoir violé les dispositions qui régissent les conditions de renvoi de Suisse et mentionne spécifiquement l'art. 13 let. f de l'ordonnance fédérale limitant le nombre des étrangers du 6 octobre 1996 (OLE; RS 823.21; RO 1986 p. 1791 et les modifications ultérieures), abrogée avec l'entrée en vigueur de la nouvelle législation fédérale en matière d'étrangers. Il se prévaut en particulier de ce qu'il réside en Suisse depuis 2002, de ce que son intégration socio-professionnelle est bonne et de ce que l'union conjugale avec son épouse est bel et bien effective.
5.2 Le recours constitutionnel subsidiaire est irrecevable dans la mesure où le recours en matière de droit public est ouvert (cf. consid. 2.3 supra). Les griefs tirés de la procédure de renvoi et, en tant qu'applicable, de l'art. 13 let. f OLE, dont l'examen est exclu dans le cadre du recours en matière de droit public (art. 83 let. c ch. 2 et 5 LTF), ne peuvent être soulevés au titre du recours constitutionnel subsidiaire. Dans ce cadre, le recourant ne serait en effet légitimé (<ref-law>) à se prévaloir que de la violation de ses droits de partie débouchant sur un déni de justice formel, dès lors qu'il ne possède aucun droit lui permettant de s'opposer à son renvoi ni un droit à l'octroi d'une autorisation de séjour pour cas de rigueur (<ref-ruling> consid. 6 p. 197 ss; arrêts 2C_52/2010 du 14 juin 2010 consid. 3.1; 2C_761/2009 du 18 mai 2010 consid. 2.4). Or, le recourant n'invoque pas de tels griefs, de sorte que le recours constitutionnel subsidiaire doit être déclaré irrecevable aussi concernant la décision de renvoi et l'octroi d'une autorisation de séjour pour cas exceptionnel.
6. Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable.
Succombant, le recourant doit supporter les frais judiciaires (art. 65 et 66 al. 1 LTF). Il ne sera pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière de droit public est rejeté dans la mesure où il est recevable.
2. Le recours constitutionnel subsidiaire est irrecevable.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations, au Département de l'économie et au Tribunal administratif du canton de Neuchâtel Cour de droit public ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 11 octobre 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Chatton