Faits:
A. X._, né en 1982, s'est immatriculé à l'Université de Genève, en Faculté des sciences économiques et sociales, en automne 2003. Il a suivi les cours de première année à Genève, puis a accompli sa seconde année à l'Université Complutense de Madrid. En automne 2005, il s'est inscrit à l'Institut des hautes études internationales et du développement (ci-après: l'IHEID), à Genève, en vue d'obtenir une licence en relations internationales.
Parallèlement à ses études, X._ a travaillé, de février 2006 à février 2007, au sein de la Mission diplomatique du Timor-Leste auprès de l'Office des Nations Unies et des organisations internationales, à Genève, puis il a été engagé, du 26 mars au 8 novembre 2007, comme stagiaire académique auprès de l'Ambassade de Suisse à New Dehli. Enfin, du 15 janvier au 30 octobre 2008, il a été engagé, à plein temps, pour le compte de la Direction du développement et de la coopération (DDC), à Berne.
B. X._ s'est présenté aux examens finaux de quatrième année lors des sessions de février et juin 2008. Il a réussi les trois examens écrits à la première tentative et a ainsi reçu les 12 crédits accordés pour ces examens. En revanche, il a échoué deux fois à l'examen oral « Coopération, organisations et relations : questions spéciales » (ci-après: examen CORI), obtenant à chaque essai une note de 3,5, insuffisante pour recevoir les 12 crédits requis pour cet examen.
Le 15 juillet 2008, X._ s'est adressé aux professeurs qui avaient jugé sa prestation orale pour connaître les raisons de son échec et obtenir des conseils afin de mieux préparer sa dernière tentative. Le 14 août 2008, le professeur A._ lui a répondu qu'il n'était plus en possession des notes de l'examen de la session d'été et qu'il n'était pas en mesure de lui donner des indications particulières concernant sa « performance de l'époque ». Il lui a toutefois prodigué quelques conseils sur la manière de procéder, en relevant que chaque professeur avait « sa façon d'évaluer et ses préférences ».
Le 3 septembre 2008, X._ s'est présenté pour la troisième fois à l'examen CORI et a obtenu la note 3. Ce nouvel échec étant définitif, le directeur de l'IHEID a, par lettre du 18 septembre 2009, informé X._ de son élimination.
C. X._ a formé opposition contre cette décision d'élimination, en demandant à pouvoir se représenter à l'examen CORI. Se fondant sur son bon parcours académique et professionnel, il faisait valoir que son stress et son anxiété l'avaient conduit à répondre de manière hâtive et peu contrôlée aux examinateurs, lesquels l'avaient contredit avec virulence, mettant en cause notamment l'actualité de ses sources. Il disait qu'il allait entreprendre toutes les démarches utiles pour surmonter ce problème et produisait deux attestations de médecins qui le suivaient, datées du mois d'octobre 2008.
Par décision du 18 décembre 2008, le Directeur de l'IHEID a rejeté l'opposition. En ce qui concerne l'appréciation de l'examen, il s'est fondé sur le rapport de la commission des oppositions, accepté par le collège des professeurs dans sa séance du 8 décembre 2008, qui écartait toute trace d'arbitraire dans la manière dont l'examen CORI avait été évalué. Pour le reste, il a estimé que le stress et l'anxiété causés par un examen oral ne pouvaient constituer une circonstance exceptionnelle, puisqu'ils étaient le lot d'un grand nombre d'étudiants. L'intéressé ne s'était d'ailleurs préoccupé de ce problème qu'après son échec définitif.
D. X._ a recouru contre cette décision auprès du Tribunal administratif du canton de Genève, compétent, depuis le 1er janvier 2009, pour connaître des décisions sur opposition (cf. art. 163 al. 3 de la loi genevoise sur l'organisation judiciaire modifiée le 18 septembre 2008; RSGE E2 05).
Après avoir entendu les parties lors d'une audience de comparution personnelle du 3 avril 2009, le Tribunal administratif a rejeté le recours, par arrêt du 27 octobre 2009. Il a tout d'abord constaté que l'opposition avait été instruite conformément aux dispositions légales applicables et que le grief de violation du droit d'être entendu devait être rejeté, dès lors que le recourant avait pu prendre connaissance des avis des examinateurs produits devant la juridiction cantonale qui disposait du même pouvoir d'appréciation que le collège des professeurs. Sur le fond, il a estimé que l'avis émis par un examinateur, confirmé par le second, reposait sur les notes prises lors de l'examen et révélait les lacunes reprochées au recourant. Rien ne permettait ainsi de considérer que les examinateurs avaient apprécié arbitrairement les prestations du recourant. En outre, la situation de l'intéressé et son cursus ne justifiaient pas qu'il soit mis au bénéfice de circonstances exceptionnelles, de sorte que la décision d'élimination était fondée.
E. X._ forme auprès du Tribunal fédéral un recours constitutionnel subsidiaire contre cet arrêt. Il conclut, avec suite de dépens, à l'annulation de la décision prononçant son élimination de l'IHEID et à l'autorisation de se présenter une quatrième fois à l'examen oral CORI. A titre subsidiaire, il demande au Tribunal fédéral de renvoyer la cause à l'instance cantonale pour qu'elle procède à l'audition du Docteur B._ et du Directeur de la Clinique du Centre de conseil psychologique de l'Université de Genève, M. C._.
Le Tribunal administratif se réfère aux considérants et au dispositif de son arrêt et le Directeur de l'IHEID conclut au rejet du recours, dans la mesure de sa recevabilité.

Considérant en droit:
1. Le recourant a déclaré déposer un recours constitutionnel subsidiaire. Cette voie de droit suppose qu'aucun recours selon les art. 72 à 83 LTF ne soit ouvert (cf. <ref-law>), question que le Tribunal fédéral examine d'office et librement (<ref-ruling> consid. 1 p. 3).
1.1 D'après 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. Selon la jurisprudence, les décisions d'exmatriculation d'une université ou d'une haute école ou celles d'élimination d'une faculté ou d'un programme d'études peuvent tomber sous le coup de l'art. 83 let. t LTF. Encore faut-il, pour que la voie du recours en matière de droit public soit fermée, que la décision d'exmatriculation ou d'élimination soit en lien avec une évaluation des capacités de l'étudiant évincé (cf. 2D_57/2009 du 3 décembre 2009; 2D_142/2008 du 23 avril 2009 consid. 1.2; et 2C_313/2007 du 21 août 2007, consid. 2.2). Tel est bien le cas, en l'espèce, de la décision d'élimination du recourant de l'IHEID, qui a été prise en raison de son troisième échec à l'examen CORI.
Irrecevable en vertu de l'art. 83 let. t LTF comme recours en matière de droit public, le présent recours doit donc être traité comme recours de droit constitutionnel subsidiaire.
1.2 La voie du recours constitutionnel subsidiaire n'est ouverte que pour se plaindre de la violation des droits constitutionnels (<ref-law>), qu'il appartient au recourant d'invoquer et de motiver sous peine d'irrecevabilité (cf. <ref-law> applicable par renvoi de l'<ref-law>). Ce recours n'est recevable que contre les décisions finales (cf. art. 117 et 90 LTF), prises par l'autorité supérieure de dernière instance cantonale. Il s'ensuit qu'en raison de l'effet dévolutif (<ref-ruling> consid. 1.4 p. 144), le présent recours n'est pas recevable en tant qu'il conclut à l'annulation de la décision prononçant son élimination prise par le Directeur de l'IHEID. Pour le reste, déposé en temps utile (<ref-law>), par le recourant qui a un intérêt juridique à l'annulation ou à la modification de la décision attaquée, confirmant son élimination de l'IHEID (<ref-law>), le recours est en principe recevable comme recours constitutionnel subsidiaire.
1.3 Les faits litigieux se sont produits avant l'entrée en vigueur, le 17 mars 2009, de la nouvelle loi sur l'université du 13 juin 2008 (LU; RSGE C 1 30). Partant, il n'est pas contesté que le cas du recourant doit être traité selon l'ancien droit, soit le règlement interne relatif aux procédures d'opposition et de recours du 14 juin 2007 (RIOR), l'ancienne loi sur l'université du 26 mai 1973 (aLU) et l'ancien règlement sur l'université du 7 septembre 2008 (aRU). Par ailleurs, le recourant ayant débuté ses études en automne 2003, il est soumis au règlement d'études de la faculté des sciences économiques et sociales d'octobre 2003 (RE).
2. Le recourant se plaint d'une violation de son droit d'être entendu, parce qu'il n'a jamais été en mesure de se déterminer sur une appréciation détaillée de sa prestation orale et n'a pas davantage obtenu d'informations sur les réponses qui étaient attendues de lui pour réussir l'examen en cause. Il relève aussi que, malgré l'importance que représentait pour lui le résultat de son examen de septembre 2008, à l'issue de quatre années d'études menées sans aucun problème, il n'a pu prendre connaissance du courrier électronique du professeur D._ du 4 décembre 2008 que lors de la réponse de l'autorité intimée devant le Tribunal administratif. Par ailleurs, la justification rétroactive d'une note d'examen dans la procédure d'opposition constituerait également une violation du droit d'être entendu.
2.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 et de toute prise de position soumise au tribunal (<ref-ruling> consid. 2.3 p. 282; <ref-ruling> consid. 4.6 p. 104; <ref-ruling> consid. 2b p. 10), ainsi que 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).
Par exception au principe de la nature formelle du droit d'être entendu, une violation de celui-ci, pour autant qu'elle ne soit pas d'une gravité particulière, est considérée comme réparée lorsque l'intéressé jouit de la possibilité de s'exprimer librement devant une autorité de recours disposant du même pouvoir d'examen que l'autorité inférieure, et qui peut ainsi contrôler librement l'état de fait et les considérations juridiques de la décision attaquée (<ref-ruling> consid. 2.6.1 p. 285 et les arrêts cités; <ref-ruling> consid. 7.3; <ref-ruling> consid. 2b).
2.2 En l'espèce, le Tribunal administratif a constaté que les avis des examinateurs, qui s'étaient déterminés sur la prestation du recourant par écrit, sur la base de notes prises lors de l'examen, avaient été produits au cours de la procédure devant lui. Le recourant avait donc pu en prendre connaissance et l'opportunité lui avait été donnée de se prononcer à ce sujet devant l'instance de recours qui disposait du même pouvoir d'appréciation que le collège des professeurs.
D'une manière générale, le droit d'être entendu n'implique pas qu'un candidat à un examen puisse s'exprimer sur ses prestations avant une décision négative au sujet de cet examen (<ref-ruling>, consid. 2b p. 288: voir aussi arrêt 2P. 21/1993 du 8 septembre 1993, consid. 1a, publié in SJ 1994 p. 161). Avant la décision sur opposition du Directeur de l'IHEID, le recourant ne pouvait donc exiger d'avoir accès au rapport d'instruction de la commission des oppositions de l'IHEID qui avait pris en compte les avis des deux examinateurs, exprimés dans leur courriel respectif des 4 décembre 2008. Tel était aussi le cas des notes personnelles des examinateurs, qui restaient leur propriété et ne constituaient qu'une aide afin leur permettre de donner des informations précises, s'ils étaient amenés à se déterminer par écrit sur des prestations d'examen (cf. arrêt 2P.23/2004 du 13 août 2004, consid. 2.4). A cet égard, l'Université a expliqué, lors de l'audience de comparution personnelle du 3 avril 2009, que la pratique des professeurs était de ne pas garder leurs notes personnelles au-delà du délai d'un mois après l'examen, sauf en cas d'opposition ou de contestation.
Dans cette situation, il faut admettre que le droit d'être entendu du recourant a été respecté, puisque, devant le Tribunal administratif, soit une autorité judiciaire disposant d'un plein pouvoir d'examen, il a eu connaissance du rapport d'instruction de la commission des oppositions, ainsi que des avis des deux professeurs qui l'ont interrogé lors de la session d'automne 2008 et qu'il a eu ensuite la faculté de se déterminer à leur propos (cf. arrêt 2D_130/2008 du 13 février 2009, consid. 3).
3. Au fond, le recourant invoque une violation de l'interdiction de l'arbitraire et du principe de l'égalité de traitement. Il fait valoir que son examen oral a été apprécié de façon subjective par les examinateurs, dès lors qu'il n'existe aucune grille de corrections préalable imposant les questions qui devaient être impérativement abordées par le candidat pour obtenir la moyenne. Il aurait ainsi été livré à l'arbitraire le plus absolu d'un professeur, suivi sans esprit critique par son co-examinateur. Il reproche aussi à la juridiction cantonale ne n'avoir pas retenu que la justification médicale invoquée constituait une situation exceptionnelle au sens de l'art. 22 al. 3 aRU.
3.1 Aux termes de l'art. 63D al. 3 aLU, 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 al. 1 aRU 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. L'alinéa 2 de cette disposition précise qu'un étudiant est éliminé, notamment s'il échoue à un examen ou à une session d'examens auxquels il ne peut plus se présenter en vertu du règlement d'études.
Selon l'art. 22 al. 3 aRU, "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".
3.2 Une décision est arbitraire lorsqu'elle contredit clairement la situation de fait, qu'elle viole gravement une norme ou un principe juridique clair et indiscuté ou qu'elle heurte d'une manière choquante le sentiment de la justice et de l'équité. A cet égard, le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si elle apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs ou en violation d'un droit certain. De plus, pour qu'une décision soit annulée, il ne suffit pas que sa motivation soit insoutenable; il faut encore que cette décision soit arbitraire dans son résultat (<ref-ruling> consid. 3.1 p. 266, 140 consid. 5.4 p. 148), ce qu'il appartient au recourant de démontrer, conformément à l'<ref-law> (<ref-ruling> consid. 3.1 p. 153). En outre, en matière de résultats d'examens, le Tribunal fédéral fait preuve d'une réserve toute particulière. Il se borne à vérifier que l'autorité chargée d'apprécier l'examen ne se soit pas laissé guider par des considérations étrangères à l'examen ou de toute évidence insoutenables pour d'autres raisons (<ref-ruling> consid. 3.1 p. 473 et les références; voir aussi arrêt 2P.205/2006 du 19 décembre 2006, consid. 3.3, publié in SJ 2007 p. 405).
3.3 Il est vrai que l'Université a admis, lors de l'audience de comparution personnelle du 3 avril 2009, qu'il n'existait aucune grille commune de corrections ou de corrigés-types, mais elle a expliqué qu'en fonction des domaines choisis par les étudiants parmi les sept sujets proposés pour l'examen CORI, plusieurs professeurs de l'IHEID étaient susceptibles de faire passer l'examen et qu'il y avait alors une réunion permettant d'établir un syllabus. Cette pratique n'est nullement critiquable et n'implique pas qu'un candidat soit prétérité en fonction du professeur qui l'interroge. Sur ce point, le recourant n'explique d'ailleurs pas en quoi il aurait été victime d'une inégalité de traitement, de sorte que son recours est irrecevable en tant qu'il porte sur une violation de l'art. 8 Cst. (<ref-law>). Il paraît également normal que, comme l'a expliqué l'Université, un professeur ne conserve plus ses notes un mois après l'examen, sauf en cas d'opposition. Le recourant ne saurait à cet égard revenir sur son examen de juin 2008 qu'il n'avait d'ailleurs pas contesté.
En ce qui concerne le dernier examen de septembre 2008, l'avis du professeur D._, qui a interrogé le recourant, relève les graves lacunes de ce dernier dans le domaine qu'il devait traiter, portant sur le régionalisme des droits de l'homme, en particulier le fait qu'il ne connaissait pas l'existence de la Cour interaméricaine des droits de l'homme qui avait beaucoup développé sa jurisprudence durant la dernière décennie. Les questions posées étaient destinées à aiguiller le recourant sur les points essentiels à développer et rien ne permet de supposer que ce professeur ait été prévenu à l'encontre du recourant. Le second professeur s'est certes rallié par écrit à l'avis du premier, mais il ressort de leur courriel respectif du 4 décembre 2008, qu'ils avaient encore l'intention d'en discuter. En outre, dans sa séance du 9 décembre 2008, le collège des professeurs a aussi discuté du cas du recourant sur la base du rapport d'instruction de la commission des oppositions de l'IHEID, qu'il a accepté. Dans ces circonstances, on ne peut dire qu'en confirmant le contrôle des connaissances du recourant et l'appréciation de ses prestations par l'autorité administrative, les juges cantonaux seraient tombés dans l'arbitraire. Il convient d'ajouter que le recourant a travaillé à plein temps, du 15 janvier au 30 octobre 2008, auprès de la DDC à Berne. Il a ainsi pris le risque de se présenter une troisième fois à l'examen CORI en cours d'emploi, après deux échecs consécutifs aux sessions de février et juin 2008, alors qu'il savait qu'il s'agissait de sa dernière tentative et que la réussite à cet examen comptait autant que celle des trois examens écrits dans l'obtention des 24 crédits affectés aux examens finaux (cf. art. IV ch. 2 du règlement du programme de licence en relation internationales entré en vigueur le 23 octobre 2006).
3.4 L'art. 22 al. 3 aRU imposait au Directeur de l'IHEID de se prononcer sur les circonstances exceptionnelles invoquées par le recourant, ce qu'il a fait dans sa décision du 18 décembre 2008. A cet égard, le Tribunal administratif a considéré à juste titre que le recourant s'était aperçu tardivement de ses problèmes de stress et d'anxiété aux examens oraux et a confirmé l'avis du Directeur de l'IHEID selon lequel les problèmes du recourant étaient le lot de plusieurs étudiants lorsqu'ils passaient des examens, a fortiori lorsqu'il s'agissait d'une dernière tentative. Il n'y a donc pas lieu de lui renvoyer l'affaire pour qu'il procède à l'audition des deux témoins qui avaient attesté de la situation du recourant au mois d'octobre 2008, ainsi que le requiert ce dernier dans ses conclusions subsidiaires. Au surplus, le Tribunal administratif s'est référé à sa jurisprudence qui considère notamment que le fait de se trouver en fin d'études ne constitue pas une circonstance exceptionnelle. Il a aussi estimé que le fait de reconnaître le cursus du recourant en prenant en compte les stages effectués, au demeurant conseillés pendant les études, reviendrait à mettre en danger l'égalité de traitement entre étudiants. Cette argumentation est parfaitement soutenable et ne saurait être sanctionnée sous l'angle de l'arbitraire.
4. Au vu de ce qui précède, le recours doit être rejeté dans la mesure de sa recevabilité, avec suite de frais à la charge du recourant (<ref-law>).

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'500 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du recourant, à l'Institut de hautes études internationales et du développement, à l'Université de Genève et au Tribunal administratif du canton de Genève.
Lausanne, le 26 avril 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