Faits:
A. X._, né en 1970, a obtenu un diplôme d'études approfondies auprès de l'Institut universitaire d'études de développement (ci-après: l'IUED), le 7 octobre 2003. Il est inscrit en programme doctoral depuis octobre 2004. Après avoir obtenu plusieurs prolongations de délai pour présenter son mémoire préliminaire de thèse, il a soutenu ce dernier, le 29 mars 2007, devant le jury qui en a constaté à l'unanimité l'insuffisance, mais l'a néanmoins autorisé à présenter une nouvelle version. Un délai à fin juin 2007 a été convenu avec lui, sa directrice de thèse, A._, et le codirecteur de thèse, B._, sollicité pour renforcer le soutien méthodologique, pour présenter cette nouvelle version.
Sans nouvelle de l'intéressé, A._ l'a contacté par courrier électronique du 12 juillet 2007, mais X._ n'a pas répondu. Le 27 septembre 2007, B._ lui a rappelé les délais prévus par le règlement d'études et l'a informé de son intention d'entamer une procédure d'exclusion du programme doctoral. A la demande de l'étudiant, un ultime délai au 21 octobre 2007 lui alors été accordé pour rendre son mémoire préliminaire.
Constatant que ce délai n'avait pas été respecté, le Directeur de l'IUED a prononcé l'élimination de X._ du programme doctoral, par décision du 3 décembre 2007. Ce prononcé a été confirmé sur opposition, le 24 avril 2008, par le Directeur de l'Institut des hautes études internationales et du développement (ci-après: l'IHEID - qui a englobé l'IUED au 1er janvier 2008 - ), qui se fondait sur le rapport d'instruction de la Commission des oppositions et des recours de l'Université de Genève du 3 avril 2008.
B. X._ a fait opposition à cette décision auprès de la Commission de recours de l'Université de Genève (ci-après: la Commission de recours), en soutenant essentiellement que seul l'échec à son second mémoire pourrait justifier son élimination, dès lors qu'aucun délai réglementaire ne lui était applicable. Ses observations du 14 août 2008 sur les déterminations de l'IHEID ont été acceptées à titre de réplique.
Par décision du 11 novembre 2008, la Commission de recours a rejeté le recours, au motif que l'élimination du recourant pour dépassement du délai d'études - qui arrivait à échéance au plus tard en novembre 2005 et avait été prolongé jusqu'au 21 octobre 2007 - ne souffrait d'aucune critique. Il n'y avait pas lieu non plus de tenir compte de circonstances exceptionnelles, non réalisées en l'espèce.
C. X._ forme un recours constitutionnel subsidiaire auprès du Tribunal fédéral et conclut à la modification ou à l'annulation de la décision de la Commission de recours du 11 novembre 2008, et partant, de celle du Directeur de l'IHEID du 3 décembre 2007, afin qu'il puisse présenter sa deuxième version du mémoire préliminaire de thèse.
La Commission de recours, dont les compétences ont été transférées au Tribunal administratif du canton de Genève, persiste dans les considérants et le dispositif de sa décision. L'IHEID conclut au rejet du recours, dans la mesure où il est recevable.
D. Par ordonnance présidentielle du 17 mars 2009, la demande d'effet suspensif contenue dans le recours a été admise.

Considérant en droit:
1. Le recourant a déposé un recours constitutionnel subsidiaire, en se fiant aux indications de la Commission de recours, et déclare limiter son recours à la question du dépassement du délai pour déposer son mémoire préliminaire de thèse, qui a motivé son élimination du programme doctoral de l'IHEID. Il y a lieu toutefois d'examiner d'office et librement si la voie du recours en matière de droit public est ouverte (<ref-ruling> consid. 1 p. 3).
1.1 En vertu de l'art. 83 let. t LTF, le recours en matière de droit public n'est pas ouvert à l'encontre des décisions sur le résultat d'examens ou d'autres évaluations des capacités, notamment en matière de scolarité obligatoire, de formation ultérieure ou d'exercice d'une profession. Une décision d'élimination d'une faculté ou d'un programme d'études peut tomber sous le coup de l'art. 83 let. t LTF si elle est directement en lien avec une évaluation des capacités de l'étudiant évincé. A contrario, une exmatriculation ou une élimination qui n'est pas liée à un résultat d'examen ou à une autre évaluation des capacités n'est pas couverte par la clause d'irrecevabilité de l'art. 83 let. t LTF (cf. arrêt 2D_142/2008 du 23 avril 2009, consid. 1.2 et les arrêts cités). Il en va ainsi, par exemple, de la question de savoir si un étudiant peut se faire exclure d'une faculté pour n'avoir pas déposé un mémoire dans les délais réglementaires (arrêt 2C_549/2008 du 7 novembre 2008). En l'espèce, l'élimination du recourant est fondée sur le non-respect des délais accordés. Il s'ensuit que la voie du recours en matière de droit public est ouverte, ce qui exclut la recevabilité du recours constitutionnel subsidiaire (<ref-law> a contrario). L'indication erronée de la voie de droit ne nuit toutefois pas au recourant, car le litige relève du droit cantonal. Dans le cadre d'un recours en matière de droit public, l'application de ce droit ne peut être revue que sous l'angle de la violation des droits constitutionnels (cf. <ref-law>; cf. infra consid. 1.4). Partant, le recourant qui a agi par la voie du recours constitutionnel subsidiaire ne s'est pas vu privé de la possibilité d'invoquer des griefs qui auraient été possibles, s'il avait su qu'il pouvait agir par le biais du recours en matière de droit public.
1.2 La décision prononçant l'élimination du recourant du programme doctoral de l'IHEID est une décision finale (<ref-law>). Dans la mesure où elle a été rendue avant le 1er janvier 2009, soit dans le délai transitoire de deux ans à compter de l'entrée en vigueur de la loi sur le Tribunal fédéral (<ref-law>), la question de savoir si la Commission de recours constitue un tribunal supérieur au sens de l'<ref-law>, entrant dans la catégorie des autorités cantonales de dernière instance visées par l'art. 86 al. 1 let. d LTF, peut demeurer indécise (arrêt 2D_130/2008 du 13 février 2009 consid. 1.3). Du reste, en 2009, les compétences de cette Commission ont été transférées au Tribunal administratif du canton de Genève (voir art. 36 al. 1 du règlement relatif à la procédure d'opposition au sein de l'Université de Genève du 16 mars 2009).
1.3 Déposé en temps utile (<ref-law>), par le destinataire de la décision attaquée, qui a un intérêt digne de protection à son annulation (art. 89 al. 1 let. c LTF), l'acte de recours est donc en principe recevable comme recours en matière de droit public.
1.4 Sous réserve d'exceptions (cf. art. 95 let. c et d LTF) non réalisées en l'espèce, le Tribunal fédéral ne contrôle pas l'application du droit cantonal en tant que tel, mais examine uniquement si celle-ci viole le droit fédéral au sens de l'<ref-law>, qui comprend les droits constitutionnels des citoyens. Lorsque, comme dans le présent recours, il est question de la violation de droits fondamentaux, ainsi que de l'application arbitraire du droit cantonal, le Tribunal fédéral se prononce uniquement sur les griefs invoqués et motivés de façon suffisante par le recourant (cf. <ref-law>; <ref-ruling> consid. 1.4.2 p. 254; <ref-ruling> consid. 6 p. 397).
2. Le recourant prétend tout d'abord que son élimination du programme doctoral de l'IHEID ne reposerait sur aucune disposition réglementaire, de sorte que la Commission de recours serait tombée dans l'arbitraire et aurait abusé de son pouvoir d'appréciation en confirmant la décision d'élimination du Directeur de l'IHEID.
2.1 Aux termes de l'art. 63D al. 3 de la loi genevoise sur l'université du 26 mai 1973 (LU; RSGE C 1 30), les conditions d'immatriculation, d'exmatriculation, d'inscription et d'élimination des étudiants et auditeurs sont fixées par le règlement de l'université. Intitulé "Elimination", l'art. 22 du règlement de l'université du 7 septembre 1988 (RU; RSGE C 1 30.06) dispose que l'étudiant éliminé d'une subdivision, d'une faculté ou d'une école ne peut plus s'inscrire aux enseignements de cette subdivision, de cette faculté ou de cette école (al. 1). L'alinéa 2 de cette disposition précise les deux cas d'élimination d'un étudiant, à savoir:
"a) l'étudiant qui échoue à un examen ou à une session d'examens auxquels il ne peut plus se présenter en vertu du règlement d'études;
b) l'étudiant qui ne subit pas les examens et ne termine pas ses études dans les délais fixés par le règlement d'études."
Selon l'art. 22 al. 3 RU, "la décision d'élimination est prise par le doyen de la faculté ou par le président d'école, lesquels tiennent compte des situations exceptionnelles".
2.2 L'IHEID, dans lequel est inscrit le recourant, est un institut en relation avec l'Université de Genève au sens de l'art. 7 RU (cf. art. 10 RU). Les dispositions concernant les études de doctorat ont été récemment modifiées pour l'IHEID. Son règlement d'études de doctorat (RE), entré en vigueur le 15 septembre 2008, a notamment abrogé le règlement d'étude et les clauses d'application du doctorat en études du développement du 1er décembre 2006 (ci-après: REdév.). Il prévoit toutefois, à l'art. 15 ch. 6 de ses dispositions transitoires, que les étudiants inscrits au doctorat en études du développement avant le 15 septembre 2008 sont soumis au nouveau règlement, à l'exception de l'art. 7 al. 1 et 2 et de l'art. 10 al. 1 et 2. Par ailleurs, les art. 7 al. 1 et 9 al. 1 et 2 anciens leur restent applicables. Il s'ensuit que, pour la question du délai présentement litigieuse, le recourant est bien soumis à l'ancien droit, soit aux art. 9 et 10 REdév. Selon l'art. 9 al. 1 REdév., "le candidat doit avoir présenté avec succès son mémoire préliminaire de thèse au plus tard deux semestres à dater de son immatriculation", le Directeur de l'Institut pouvant accorder une prolongation du délai dans les cas exceptionnels (art. 9 al. 3). Quant à l'art. 10 al. 1 REdév., il énumère les deux cas dans lesquels l'élimination du candidat est prononcée, soit le non-respect des délais prévus à l'art. 9 et la non-acceptation du mémoire préliminaire à la deuxième tentative (lettre b).
Contrairement au nouvel art. 10 al. 1 RE, qui permet de prolonger le délai pour présenter le mémoire préliminaire de thèse après un premier échec du troisième au quatrième semestre au plus tard, l'art. 9 al. 1 REdév. ne prévoyait pas cette possibilité en cas d'échec. Cette absence de prolongation n'a cependant pas nui au recourant dans la mesure où, comme l'a constaté la Commission de recours, le délai impératif au 21 octobre 2007 qui lui avait été fixé dépassait largement le délai de l'art. 9 al. 1 REdév., même si l'on tient compte de la date d'immatriculation la plus favorable au recourant, soit octobre 2004.
En effet, avant et après l'échec de sa première tentative de présentation de son mémoire complémentaire, le 29 mars 2007, le recourant a bénéficié de plusieurs prolongations de délai, la dernière impérativement fixée au 21 octobre 2007. Il se trouvait donc déjà en dehors du délai de deux semestres dès l'immatriculation prévu par l'art. 9 al. 1 REdév. Ces prolongations n'ont donc pu lui être accordées que sur la base de l'art. 9 al. 3 REdév., selon lequel le Directeur de l'IUED peut accorder une prolongation dans les cas exceptionnels. Cela ne signifie pas encore que la Commission de recours devait faire abstraction de la réglementation usuelle en matière de délai de présentation du mémoire préliminaire, pour apprécier le bien-fondé de l'élimination du recourant. On ne saurait en effet suivre ce dernier lorsqu'il se plaint d'arbitraire et d'abus du pouvoir d'appréciation de la Commission de recours, parce qu'elle a estimé que son élimination se justifiait, au motif qu'il avait dépassé le délai réglementaire d'études. Le fait qu'il a obtenu à plusieurs reprises et à titre exceptionnel de pouvoir différer la remise de son mémoire préliminaire de thèse, tant pour la première tentative que pour la seconde, ne pouvait en effet avoir pour résultat de le soustraire à toute application de l'art. 10 al. 1 let. a REdév. prévoyant l'élimination définitive du candidat pour non-respect des délais prévus à l'art. 9 REdév. En outre, lors de l'ultime prolongation au 21 octobre 2007, il avait été dûment averti que, sans nouvelle de sa part à cette date, une procédure d'élimination serait entamée. Toute autre interprétation reviendrait à privilégier sans raison un candidat obtenant une prolongation de délai pour cas exceptionnels, en le dispensant de respecter le délai ainsi prolongé.
2.3 Dans ces conditions, la Commission de recours pouvait retenir sans arbitraire que le recourant se trouvait bien, au mois de décembre 2007, en situation de dépassement du délai d'études, ce qui entraînait son élimination, conformément aux art. 10 al. 1 let. a REdév. et 22 al. 2 let. b RU.
2.4 Pour le reste le recourant ne prétend pas que la Commission de recours aurait retenu arbitrairement qu'au mois de décembre 2007, il ne pouvait plus bénéficier de circonstances exceptionnelles, au sens des art. 9 al. 3 REdév. ou 22 al. 3 RU.
3. Le recourant se plaint aussi de violations de l'art. 29 al. 1 et 2 Cst., parce que la Commission de recours, à la fois juge et partie, ne l'aurait pas traité équitablement et aurait violé son droit d'être entendu en laissant de côté les éléments pertinents.
3.1 Le droit d'être entendu est l'un des aspects de la notion générale de procès équitable. Il comprend notamment le droit pour l'intéressé de prendre connaissance du dossier (<ref-ruling> consid. 2b p. 10), de s'exprimer sur des éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique (<ref-ruling> consid. 3.1 p. 277), ainsi que le droit de prendre connaissance de toute prise de position soumise au tribunal et de se déterminer à ce propos (<ref-ruling> consid. 4.6 p. 104).
Il faut tout d'abord souligner qu'en l'espèce, la Commission de recours a respecté le droit d'être entendu du recourant en lui transmettant les déterminations du Directeur de l'IHEID et en acceptant ensuite ses observations comme réplique (sur ce point, voir arrêt 2D_130/2008 du 13 février 2009, consid. 3). Au surplus, le recourant ne dit pas sur quels points la Commission de recours l'aurait empêché de s'exprimer ou aurait omis de tenir compte d'éléments pertinents. Pour autant qu'elle soit recevable au regard des exigences de l'<ref-law> et de la jurisprudence (<ref-ruling> consid. 1.3 p. 67; <ref-ruling> consid. 2.1 p. 143), toute son argumentation revient en fait à contester l'application des art. 9 al. 1 et 10 al. 1 let. a REdév. à son cas, dont on vient de voir qu'elle échappait au grief d'arbitraire. Le recours ne peut dès lors qu'être rejeté dans la mesure de sa recevabilité, en tant qu'il porte sur une violation de l'art. 29 al. 1 et 2 Cst.
4. Au vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable, avec suite de frais à la charge du recourant (<ref-law>).

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 à 1'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au recourant, à l'Institut de hautes études internationales et du développement et à la Commission de recours de l'Université de Genève.
Lausanne, le 25 mai 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Rochat