Faits:
A. X._ (ci-après: l'intéressé), ressortissant algérien né le ***1962, est entré en Suisse le 6 avril 1990 et y a résidé sans autorisation jusqu'en janvier 1991. Ayant épousé A._, ressortissante helvétique, le 1er février 1991, il a obtenu une autorisation de séjour par regroupement familial, laquelle a été régulièrement prolongée jusqu'au 1er février 1994. Ce premier mariage a été dissous par le divorce en date du 17 mars 1994, le couple étant néanmoins séparé depuis le mois de mai 1993.
B. Eu égard à la nouvelle situation matrimoniale de l'intéressé, l'Office de la population de la République et canton de Genève (ci-après: l'Office cantonal de la population) a informé l'intéressé de son intention de ne pas renouveler ladite autorisation. Ce dernier ayant toutefois contracté un nouveau mariage le 23 septembre 1994 avec une autre citoyenne suisse, B._, l'Office cantonal de la population lui a délivré un nouveau titre de séjour en décembre 1994. Cette seconde union s'est également soldée par un divorce, lequel a été prononcé le 3 septembre 1998. La cessation de la vie commune remontait déjà au 1er mars 1996.
Le 1er décembre 1998, l'Office cantonal de la population a refusé de renouveler le permis de séjour de l'intéressé, décision dont il s'est plaint devant la Commission cantonale de recours de police des étrangers. Par décision du 21 mars 2000, cette dernière a confirmé la décision de première instance. Un recours ultérieur auprès du Tribunal fédéral a été déclaré irrecevable le 21 août 2000, l'intéressé s'étant également fait impartir un délai pour quitter le territoire suisse au 29 octobre 2000. Il ne s'est pas soumis à cette injonction.
Le 18 septembre 2001, X._ a épousé en troisièmes noces C._, ressortissante suisse. Son nouveau statut a débouché sur l'octroi d'une nouvelle autorisation de séjour le 26 juin 2002. L'intéressé a néanmoins quitté le domicile conjugal en septembre 2003 déjà, le couple étant alors séparé. Depuis le 20 mars 2006, les époux sont soumis à des mesures de protection de l'union conjugale. Aucune procédure de divorce n'a été entamée.
C. Le 12 octobre 2006, l'Office fédéral des migrations a informé X._ de son intention de refuser d'approuver la prolongation de l'autorisation de séjour, en dépit du préavis favorable de l'Office cantonal de la population. Cette procédure a débouché sur une décision de l'Office fédéral des migrations de refuser d'approuver la prolongation de l'autorisation de séjour. En outre, en date du 28 décembre 2006, l'autorité fédérale a fixé à l'intéressé un délai de départ de Suisse au 22 mars 2007.
A l'encontre de cette décision, l'intéressé a déposé un recours auprès du Tribunal administratif fédéral en date du 31 janvier 2007.
Le 28 janvier 2010, le Tribunal administratif fédéral a rejeté ce recours. En substance, il a retenu qu'il était abusif de se prévaloir du mariage avec C._, dans la mesure où les époux étaient séparés depuis près de 7 ans, pour tenter d'obtenir une autorisation de séjour fondée sur le regroupement familial auquel l'art. 7 al. 1 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113) donne droit. Il a laissé ouverte la question de savoir si, conformément aux affirmations de C._, ce mariage n'était que de complaisance. Le Tribunal administratif fédéral a aussi nié le droit à une autorisation fondée sur l'art. 4 LSEE, les conditions autorisant l'administration à octroyer un titre de séjour fondé sur cette norme n'étant pas remplies.
D. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt rendu le 28 janvier 2010 par le Tribunal administratif fédéral et de dire que l'Office fédéral des migrations ne pouvait pas lui refuser la prolongation de son autorisation de séjour. Il se plaint de la violation de l'art. 7 al. 1 LSEE. Il n'y aurait pas d'abus de droit à se prévaloir du mariage formel avec C._, en dépit de la durée de la séparation. Enfin, les conditions d'octroi d'une autorisation fondée sur l'art. 4 LSEE seraient réunies au regard de son intégration personnelle et professionnelle en Suisse.
Le Tribunal administratif fédéral ne s'est pas prononcé. L'Office fédéral des migrations a conclu à son rejet.

Considérant en droit:
1. Selon l'art. 126 al. 1 de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20), les demandes déposées avant l'entrée en vigueur de cette loi, le 1er janvier 2008, sont régies par l'ancien droit. L'ancien droit demeure applicable à toutes les procédures initiées en première instance avant le 1er janvier 2008, indépendamment du fait qu'elles aient été ouvertes d'office ou sur demande (arrêt 2C_745/2008 du 24 février 2009, consid. 1.2.3).
En l'espèce, c'est par courrier du 12 octobre 2006 que l'Office fédéral des migrations a averti le recourant qu'il ne comptait pas prolonger son autorisation de séjour étant donné qu'il ne vivait plus de manière régulière avec son épouse. Ainsi que l'a justement relevé le Tribunal administratif fédéral, le cas demeure donc régi par l'ancien droit.
2. Selon l'art. 83 let. c ch. 2 LTF, le recours est irrecevable contre une autorisation à laquelle ni le droit fédéral ni le droit international ne donne droit.
Lorsque le recours est fondé sur l'art. 7 al. 1 LSEE, pour juger de sa recevabilité, seule est déterminante la question de savoir si un mariage au sens formel existe (cf. arrêt 2C_29/2009 du 29 mai 2009, consid. 2.1; <ref-ruling> consid. 1b p. 266). Le recourant est toujours formellement marié à une suissesse, de sorte que le recours en matière de droit public est recevable sous cet angle.
3. 3.1 Le droit du conjoint étranger marié à un(e) ressortissant(e) suisse d'obtenir une autorisation de séjour au titre du regroupement familial, tel que prévu à l'art. 7 al. 1 LSEE, n'est pas absolu. Il peut notamment être refusé lorsque le mariage n'a pas pour but de créer une union conjugale et ne constitue pas le fondement de la vie commune des époux (cf. <ref-ruling> consid. 3a p. 6). Tel est en particulier le cas d'un mariage contracté dans le seul but d'éluder les dispositions sur le séjour et l'établissement des étrangers (mariage fictif; cf. art. 7 al. 2 LSEE) ou d'un mariage vidé de toute substance dont l'invocation vise seulement à obtenir l'octroi ou la prolongation d'une autorisation de séjour (abus de droit; cf. <ref-ruling> consid. 4.2 p. 117; <ref-ruling> consid. 5a p. 56 s. et les références citées). L'existence d'un éventuel abus de droit dans un cas particulier doit être appréciée avec retenue et n'être admise que restrictivement; seul l'abus manifeste d'un droit doit être sanctionné (cf. <ref-ruling> consid. 4a p. 103). En particulier, 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 (cf. <ref-ruling> consid. 3 p. 149 ss). En revanche, il y a abus de droit, selon la jurisprudence, lorsque le conjoint étranger invoque un mariage n'ayant qu'une existence formelle dans le seul but d'obtenir une autorisation de séjour, car ce but n'est pas protégé par l'art. 7 al. 1 LSEE (cf. <ref-ruling> consid. 4a p. 103 s.). Pour admettre cette hypothèse, il convient de se fonder sur des éléments concrets indiquant que les époux ne veulent pas (ou plus) mener une véritable vie conjugale et que le mariage n'est maintenu que pour des motifs de police des étrangers. L'absence de cohabitation pendant une période significative constitue un indice permettant de dire que les époux ne veulent plus mener une véritable vie conjugale (arrêt 2C_326/2009 du 16.10.2009, consid. 3.1; <ref-ruling> consid. 10.3 p. 135 s.). Le Tribunal fédéral a notamment retenu qu'après une séparation des époux de deux ans, le lien conjugal devait être considéré comme vidé de son contenu, sauf circonstances particulières (<ref-ruling> consid. 10.4 p. 137). Les causes et les motifs de la rupture ne jouent en principe pas de rôle (<ref-ruling> consid. 4.2 p. 117).
3.2 En l'espèce, il est constant que les époux ne vivent plus ensemble depuis le mois de septembre 2003, donc depuis près de sept ans. L'épouse a déclaré ne pas avoir l'intention de reprendre la vie commune et souhaiter divorcer; le recourant a également affirmé, le 20 décembre 2005, ne pas envisager la reprise de la vie commune, "du moins pas pour l'instant".
Dans de telles circonstances, le Tribunal administratif fédéral a correctement appliqué le droit fédéral en concluant à l'existence d'un abus de droit à invoquer l'art. 7 al. 1 LSEE. Le fait que le recourant se conforme à une décision judiciaire l'obligeant à verser une pension alimentaire à son épouse ne change rien à ce constat. Le grief de violation de l'art. 7 LSEE doit donc être rejeté.
4. Pour le surplus, le recourant fait valoir qu'il est bien intégré dans le monde du travail, qu'il paie ses pensions alimentaires et qu'il séjourne en Suisse depuis un certain nombre d'années en se conformant aux lois suisses. Ce faisant, le recourant fait référence à l'art. 4 LSEE, aux termes duquel les autorités compétentes statuent librement, dans le cadre des prescriptions légales et des traités avec l'étranger, sur l'octroi ou le refus d'autorisations de séjour ou d'établissement. Cette disposition ne confère aucun droit (<ref-ruling> consid. 2.3 p. 189; <ref-ruling> consid. 2.1 p. 284), de sorte que le recours est irrecevable sous cet angle (art. 83 let. c ch. 2 LTF).
5. 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 à 66 al. 1 LTF) et n'a pas droit à une indemnité de dépens.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du recourant, à l'Office fédéral des migrations et au Tribunal administratif fédéral, Cour III.
Lausanne, le 9 juin 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Dubey