Faits:
A. A.a Le 21 septembre 2005, Y._ AG (ci-après: l'intimée), société de droit allemand en liquidation, représentée par son administrateur judiciaire, a introduit une procédure d'arbitrage (ci-après: l'arbitrage BIT) à l'encontre de l'Etat X._ (ci-après: le requérant). Elle imputait à celui-ci diverses violations d'un Traité d'investissement le liant à la République fédérale d'Allemagne, violations ayant eu pour effet de réduire la valeur de sa participation dans une société publique ..., dénommée Z._, à qui le requérant avait accordé, en 1989, une concession pour la construction et l'exploitation d'un tronçon d'autoroute à péage.
En décembre 2005, l'intimée a initié une procédure d'arbitrage contre Z._ en vue d'obtenir le paiement de factures relatives aux travaux de construction de ce tronçon d'autoroute exécutés par elle.
A.b En date du 3 décembre 2006, l'intimée, d'une part, ainsi que S._ et son fils T._ (ci-après désignés collectivement: S._), d'autre part, ont conclu un contrat, soumis au droit suisse, dont l'objet principal était la vente par l'intimée de sa participation de 9,87% dans Z._ aux prénommés, lesquels étaient déjà actionnaires, à hauteur de 30%, de cette société et membres de son conseil d'administration (ci-après: le contrat de 2006). Le prix de vente des actions, fixé à 10 millions d'euros, était payable en trois tranches, les 15 janvier, 31 mars et 30 décembre 2007. Selon l'art. 4 du chapitre A dudit contrat, à réception du paiement de la deuxième tranche, l'intimée et S._ se consulteraient régulièrement au sujet de l'arbitrage BIT. Cependant, la décision ultime de mettre un terme à cet arbitrage reviendrait à S._. Au chapitre B du même contrat, l'intimée s'engageait à retirer sa demande d'arbitrage visant Z._ contre paiement d'un montant forfaitaire de 6 millions d'euros, ce qu'elle a fait le 22 mars 2007.
A.c Le 12 juillet 2007, l'intimée et S._ ont conclu un nouveau contrat, antidaté au 3 décembre 2006 (ci-après: le contrat de 2007), dont le contenu correspondait en grande partie à celui du contrat de 2006. A l'art. 4 du chapitre A de ce nouveau contrat, les intéressés s'engageaient à faire tout leur possible pour amener le gouvernement ... à négocier avec l'intimée un règlement amiable du litige opposant cette dernière au requérant (1er par.). Si pareille tentative ne devait pas aboutir dans un délai fixé au 31 mars 2008, les parties se rencontreraient à nouveau et se consulteraient pour décider de continuer ou non l'arbitrage BIT (2e par.). Le contrat de 2007 contenait, à son art. 17, une clause de confidentialité ne figurant pas dans le contrat de 2006.
Toujours à la date du 12 juillet 2007, l'intimée et S._ ont signé une "SIDE LETTER to the Agreement dated 03 Dec 2006" (ci-après: la Side Letter), destinée à rester strictement confidentielle. L'intimée y acceptait de mettre fin à l'arbitrage BIT, sur requête de S._, au cas où ces deux parties ne parviendraient pas à se mettre d'accord sur la continuation de l'arbitrage BIT après le 31 mars 2008, comme stipulé à l'art. 4, 2e par., du contrat de 2007.
A.d Le 20 mai 2008, l'intimée a transféré à S._ sa participation dans Z._ en exécution des contrats de 2006 et de 2007.
A.e Par lettre du 17 septembre 2008, S._ a demandé expressément à l'intimée de mettre fin à l'arbitrage BIT jusqu'au 30 septembre 2008.
L'intimée ayant refusé de donner suite à cette demande, S._ a déposé une requête d'arbitrage, le 15 octobre 2008, auprès de la Chambre de Commerce Internationale, afin de l'y contraindre (ci-après: l'arbitrage CCI). Le 23 avril 2010, il a transformé sa conclusion en exécution en une conclusion en dommages-intérêts après que l'intimée avait versé au dossier de l'arbitrage CCI la sentence rendue entre-temps dans l'arbitrage BIT (cf. let. A.f ci-après).
Le Tribunal arbitral a rendu sa sentence le 18 avril 2011. Admettant que l'intimée avait violé son obligation de mettre un terme à l'arbitrage BIT, il a néanmoins écarté les prétentions pécuniaires élevées par S._ de ce chef, au motif que l'intéressé n'avait pas réussi à établir que les parties aux contrats de 2006 et de 2007 s'étaient accordées pour inclure dans le prix de vente des titres de Z._ un montant déterminé en contrepartie du droit conféré à S._ d'exiger de l'intimée qu'elle retirât sa demande dans l'arbitrage BIT.
A.f Après avoir instruit la cause dans l'arbitrage BIT, le Tribunal arbitral ad hoc composé de trois membres, statuant le 1er juillet 2009, a condamné le requérant à verser 29,21 millions d'euros, intérêts en sus, à l'intimée.
En tant qu'ils concernent les questions de droit matériel traitées par les arbitres, les motifs qui étayent la sentence rendue à cette date ne sont pas pertinents pour les besoins de la présente cause. Il n'est donc pas nécessaire de les énoncer ici.
B. Le 14 septembre 2011, le requérant a saisi le Tribunal fédéral d'une demande de révision en vue d'obtenir l'annulation de la sentence du 1er juillet 2009 et le renvoi de la cause au Tribunal arbitral pour de nouveaux débats suivis d'une nouvelle décision quant à l'effet de l'exercice par S._, le 17 septembre 2008, de son droit d'inviter l'intimée à retirer sa demande dans l'arbitrage BIT.
Par ordonnance présidentielle du 23 novembre 2011, le requérant a été prié de verser, jusqu'au 15 décembre 2011, à la Caisse du Tribunal fédéral, le montant de 150'000 fr. en garantie des dépens qui pourraient être alloués à l'intimée. Il s'est exécuté dans le délai imparti.
Par lettre de son président du 26 janvier 2012, le Tribunal arbitral a indiqué qu'il n'entendait pas participer à la procédure de révision.
Dans sa réponse du 30 janvier 2012, l'intimée a conclu à l'irrecevabilité de la demande de révision et, subsidiairement, au rejet de celle-ci.
Le requérant a déposé une réplique, le 8 mars 2012, au terme de laquelle il a maintenu les conclusions de sa demande de révision. Il a, en outre, sollicité la comparution des quatre personnes ayant fait les déclarations écrites produites par lui sous pièces 7, 7bis, 30 et 32, pour le cas où l'intimée contesterait le contenu de ces dernières.
Dans sa duplique du 23 avril 2012, l'intimée a repris les conclusions de sa réponse.
En date du 27 juin 2012, l'intimée a adressé au Tribunal fédéral, avec une lettre explicative, la copie d'un jugement par lequel le Kammergericht de Berlin a admis sa requête d'exequatur de la sentence du 1er juillet 2009.
Le 12 juillet 2012, le requérant a informé le Tribunal fédéral, avec pièces à l'appui, qu'il a interjeté appel auprès du Bundesgerichtshof contre le jugement du Kammergericht de Berlin en requérant l'octroi de l'effet suspensif.

Considérant en droit:
1. D'après l'<ref-law>, le Tribunal fédéral rédige son arrêt dans une langue officielle, en règle générale dans la langue de la décision attaquée. Lorsque cette décision a été rendue dans une autre langue (ici l'anglais), le Tribunal fédéral utilise la langue officielle choisie par les parties. Devant le Tribunal arbitral, celles-ci se sont servies de l'anglais, tandis que, dans les mémoires qu'elles ont adressés au Tribunal fédéral, elles ont employé, qui le français (le requérant), qui l'allemand (l'intimée). Conformément à sa pratique, le Tribunal fédéral rendra, par conséquent, son arrêt en français.
2. Le siège de l'arbitrage a été fixé à Genève. L'une des parties au moins (en l'occurrence, les deux) n'avait pas son domicile en Suisse au moment déterminant. Les dispositions du chapitre 12 de la LDIP sont donc applicables (<ref-law>).
La loi sur le droit international privé (LDIP; RS 291) ne contient aucune disposition relative à la révision des sentences arbitrales au sens des <ref-law>. Le Tribunal fédéral a comblé cette lacune par voie jurisprudentielle. Les motifs de révision de ces sentences étaient ceux que prévoyait l'art. 137 OJ. Ils sont désormais visés par l'<ref-law>. Le Tribunal fédéral est l'autorité judiciaire compétente pour connaître de la demande de révision de toute sentence arbitrale internationale, qu'elle soit finale, partielle ou préjudicielle. S'il admet une demande de révision, il ne se prononce pas lui-même sur le fond mais renvoie la cause au tribunal arbitral qui a statué ou à un nouveau tribunal arbitral à constituer (<ref-ruling> consid. 2 et les références).
3. A l'appui de sa demande de révision, le requérant invoque la découverte, après coup, de faits pertinents et de moyens de preuve concluants que l'intimée lui aurait délibérément cachés pendant toute la durée de la procédure arbitrale. Il s'agit du droit inconditionnel d'exiger d'elle le retrait de sa requête introductive de l'arbitrage BIT, que l'intimée avait octroyé à S._ dans le contrat de 2006 et la Side Letter, tout en cherchant à en cacher l'existence au moyen du contrat "simulé" de 2007, droit que son bénéficiaire avait effectivement exercé en septembre 2008, après avoir acquis la participation de l'intimée dans Z._, et dont le bien-fondé a été reconnu dans l'arbitrage CCI.
Si l'on en croit le requérant, la découverte de ces faits et moyens de preuve nouveaux aurait eu lieu le 17 juin 2011 dans les circonstances suivantes. Au début de l'année 2011, S._ a souhaité acquérir les actions de Z._ appartenant au requérant afin de devenir l'actionnaire majoritaire de cette société et de l'introduire à la bourse de .... Le Procureur général de ce pays, qui avait recommandé le rejet de l'offre d'achat formulée à cette fin, a accepté de rencontrer le pollicitant à sa demande. Lors de cette entrevue, qui s'est déroulée le 14 juin 2011, S._ a informé son interlocuteur de l'existence et du contenu du contrat de 2006, des raisons pour lesquelles les parties à ce contrat en avaient extrait ultérieurement la clause concernant le droit de S._ d'exiger de l'intimée qu'elle retirât sa requête d'arbitrage, de l'exercice de ce droit par son titulaire en date du 17 septembre 2008 et de la procédure qui s'était ensuivie dans l'arbitrage CCI. Le Procureur général a exigé alors de S._ la production des pièces susceptibles de prouver ses dires. C'est ainsi qu'en date du 17 juin 2011, l'avocat de S._ a remis à un cadre supérieur du Bureau du Procureur général un ensemble de documents comprenant les pièces sur lesquelles le requérant fonde sa demande de révision. Pour étayer ses affirmations, celui-ci a adressé au Tribunal fédéral des déclarations signées par le Procureur général (pièce 7), le cadre supérieur précité (pièce 7 bis), S._ (pièce 30) et l'avocat de ce dernier (pièce 32). Il requiert, au besoin, l'audition de ces quatre personnes pour qu'elles viennent confirmer leurs déclarations respectives.
Selon le requérant, les faits invoqués par lui seraient pertinents. Aussi bien, s'ils en avaient eu connaissance en temps utile, les arbitres auraient-ils débouté l'intimée de toutes ses conclusions à plus d'un titre. Ils auraient, sans doute, constaté que le requérant était au bénéfice d'une stipulation pour autrui parfaite, au sens de l'<ref-law>, lui permettant d'exiger personnellement l'exécution de l'obligation de retirer la requête d'arbitrage que l'intimée avait souscrite, dans la Side Letter, à l'égard de S._. Ou bien auraient-ils pu admettre que, par cet accord, l'intimée avait cédé à S._ sa créance de dommages-intérêts envers le requérant sous certaines conditions suspensives - en particulier, la demande faite par le cessionnaire à la cédante de retirer sa requête d'arbitrage - et en tirer la conclusion que, ces conditions s'étant accomplies à fin septembre 2008 au plus tard, la cédante n'était plus titulaire de la créance litigieuse depuis lors, partant qu'elle profitait d'une position mal acquise (nemo auditur propriam turpitudinem allegans) en maintenant sa demande de ce chef pour tenter de s'enrichir aux dépens du requérant.
4. 4.1 En vertu de l'<ref-law>, la révision peut être demandée dans les affaires civiles si le requérant découvre après coup des faits pertinents ou des moyens de preuve concluants qu'il n'avait pas pu invoquer dans la procédure précédente, à l'exclusion des faits ou moyens de preuve postérieurs à la décision formant l'objet de la demande de révision. Sauf sur quelques points concernant la révision pour violation de la CEDH, la réglementation de l'OJ en matière de révision a été reprise dans la LTF. Certaines modifications d'ordre systématique et rédactionnel ont toutefois été apportées. Ainsi, contrairement à l'art. 137 let. b OJ, l'<ref-law> ne contient plus l'expression impropre de "faits nouveaux", mais précise qu'il doit s'agir de faits pertinents découverts après coup, à l'exclusion des faits postérieurs à l'arrêt. Il n'en demeure pas moins que, sur le fond, la jurisprudence relative aux "faits nouveaux" garde toute sa portée. Ne peuvent, dès lors, justifier une révision que les faits qui se sont produits jusqu'au moment où, dans la procédure antérieure, des faits pouvaient encore être allégués, mais qui n'étaient pas connus du requérant malgré toute sa diligence; en outre, ces faits doivent être pertinents, c'est-à-dire de nature à modifier l'état de fait qui est à la base de la décision entreprise et à conduire à une solution différente en fonction d'une appréciation juridique correcte. Il y a lieu de conclure à un manque de diligence lorsque la découverte de faits ou de moyens de preuve nouveaux résulte de recherches qui auraient pu et dû être effectuées dans la procédure précédente. On n'admettra qu'avec retenue qu'il était impossible à une partie d'alléguer un fait déterminé dans la procédure antérieure, car le motif de révision des faux nova ne doit pas servir à remédier aux omissions de la partie requérante dans la conduite du procès (arrêt 4A_763/2011 du 30 avril 2012 consid. 3.1 et les arrêts cités).
Pour les motifs prévus par l'<ref-law>, la demande de révision doit être déposée devant le Tribunal fédéral, sous peine de déchéance, dans les 90 jours qui suivent la découverte du motif de révision (art. 124 al. 1 let. d LTF). Il s'agit là d'une question qui relève de la recevabilité, et non du fond, au contraire de celle de savoir si le requérant a tardé à découvrir le motif de révision invoqué. La découverte du motif de révision implique que le requérant a une connaissance suffisamment sûre du fait nouveau pour pouvoir l'invoquer, même s'il n'est pas en mesure d'en apporter une preuve certaine; une simple supposition ne suffit pas. S'agissant plus particulièrement d'une preuve nouvelle, le requérant doit pouvoir disposer d'un titre l'établissant ou en avoir une connaissance suffisante pour en requérir l'administration. Il appartient au requérant d'établir les circonstances déterminantes pour la vérification du respect du délai précité (arrêt 4A_222/2011 du 22 août 2011 consid. 2.1 et les arrêts cités).
Au demeurant, comme la révision est une voie de droit subsidiaire par rapport au recours fondé sur l'<ref-law> (<ref-ruling> consid. 1 p. 729), il est exclu d'y invoquer un motif prévu par cette disposition et découvert avant l'échéance du délai de recours (arrêt 4A_234/2008 du 14 août 2008 consid. 2.1).
4.2 Appliqués au cas particulier, ces principes jurisprudentiels s'opposent à l'entrée en matière sur la présente demande de révision.
Le requérant soutient avoir découvert en date du 17 juin 2011 les faits et moyens de preuve nouveaux censés justifier l'admission de sa demande tendant à la révision de la sentence finale du 1er juillet 2009. Supposée avérée, pareille affirmation impliquerait que cette demande, adressée le 14 septembre 2011 au Tribunal fédéral, l'a été en temps utile, c'est-à-dire dans les 90 jours suivant la découverte du motif de révision (art. 124 al. 1 let. d LTF). A son appui, le requérant a produit quatre déclarations écrites et requis, au besoin, l'audition de leurs auteurs (cf., ci-dessus, consid. 3.1, 2e § in fine). Il n'est pas nécessaire d'administrer ce moyen de preuve, puisqu'aussi bien l'intimée ne remet pas en cause la conformité des déclarations relatées dans les titres produits avec celles prêtées à leurs auteurs respectifs. Le caractère probant de ces déclarations est une autre question. En effet, celles-ci ne correspondent pas à la réalité dès lors qu'il sera démontré, ci-après, que le requérant a eu connaissance bien plus tôt qu'il ne le dit des faits et moyens de preuve prétendument nouveaux invoqués par lui.
Les parties ont disserté longuement sur le moment précis de la découverte, par le requérant, du fait que l'intimée avait octroyé à S._ le droit d'exiger qu'elle se retirât de l'arbitrage BIT et de l'exercice effectif de ce droit par son titulaire. Toutefois, pour statuer sur la recevabilité ratione temporis de la demande de révision, seul importe le point de savoir si cette découverte remonte ou non à une date antérieure de plus de 90 jours à celle du dépôt de ladite demande. Dans l'affirmative, cette dernière devra être déclarée irrecevable, que la découverte du motif de révision ait eu lieu 91 jours, six mois ou deux ans avant l'introduction de la procédure ad hoc. Or, tel est bien le cas.
Après avoir examiné les explications détaillées fournies par les parties dans leurs diverses écritures, la Cour de céans arrive à la conclusion que c'est au plus tard à fin avril 2009 que le requérant a découvert le motif avancé à l'appui de sa demande de révision. Les pièces annexées à cette demande n'autorisent pas une autre conclusion. Il en appert, plus précisément, que, dans une lettre que ses conseils ... avaient adressée le 23 avril 2009 au président du Tribunal arbitral, le requérant affirmait avoir été informé par S._ que ce dernier avait initié une procédure arbitrale contre l'intimée pour cause de violation du contrat de 2007 annexé à ladite lettre (l'arbitrage CCI), qu'il avait demandé au tribunal arbitral saisi d'ordonner à l'intimée de mettre fin à l'arbitrage BIT et qu'il était disposé à fournir des explications au Tribunal arbitral pour autant que sa position dans l'arbitrage CCI ne s'en trouvât point compromise; le requérant ajoutait, dans la même missive, qu'il estimait contraires aux règles de la bonne foi l'introduction et le maintien, par l'intimée, de la procédure arbitrale BIT en violation du contrat précité (pièce n° 24 requérant). Invitée par le président du Tribunal arbitral à se déterminer sur cette lettre, l'intimée a confirmé, le 27 avril 2009, par l'entremise de son avocat, l'existence et l'objet de l'arbitrage CCI; elle a, en outre, contesté le reproche qui lui était fait d'avoir introduit et maintenu cette procédure de mauvaise foi (pièce n° 25 requérant). Dans une lettre envoyée le 1er mai 2009 au président du Tribunal arbitral par ses mandataires, le requérant a réitéré ce reproche au motif que l'intimée aurait vendu sa participation dans Z._ à S._ après avoir convenu avec ce dernier du paiement d'un certain montant en contrepartie de son retrait de l'arbitrage BIT; il ajoutait que, à ses yeux, l'information touchant l'arbitrage CCI était importante et pertinente relativement à l'arbitrage BIT, de sorte qu'il convenait de la prendre en considération (pièce n° 26 requérant). Quant au Tribunal arbitral, il fait expressément état de ces différents courriers dans sa sentence finale (p. 18 à 21, nos 1.73 à 1.84). Après quoi, il expose les cinq motifs qui l'ont conduit à ne pas tenir compte des lettres précitées du requérant et à poursuivre la procédure pendante (p. 21 à 23, nos 1.85, let. a-e, et 1.86).
Contrairement à ce que soutient le requérant, on ne voit pas en quoi le fait qu'il n'aurait prétendument pas eu connaissance de la Side Letter avant le prononcé de la sentence du 1er juillet 2009 serait d'une quelconque pertinence du moment qu'il est établi, comme on vient de le relever, qu'il savait, au plus tard à fin avril 2009, que S._ avait introduit une procédure arbitrale contre l'intimée en reprochant à celle-ci d'avoir violé l'engagement qu'elle avait pris envers lui de se retirer de l'arbitrage BIT s'il le lui demandait, c'est-à-dire en invoquant l'obligation même que l'intimée avait souscrite dans la Side Letter.
Il n'apparaît pas non plus que le requérant n'eût pas été en mesure de requérir en temps utile l'administration de preuves quant au contenu et à la portée des accords conclus par l'intimée et S._ relativement à l'arbitrage BIT, notamment en sollicitant l'audition de cette personne, ce que le Tribunal arbitral a du reste souligné dans sa sentence (p. 22, n° 1.85, let. d), quitte à réclamer l'aide de l'autorité judiciaire compétente au besoin (cf. <ref-law>), voire à se plaindre de la violation de son droit à la preuve, par la voie d'un recours en matière civile au Tribunal fédéral fondé sur l'art. 190 al. 2 let. d LDIP, au cas où le Tribunal arbitral aurait rejeté sa requête ad hoc sans raison valable dans sa sentence finale ou l'aurait tout simplement ignorée.
La présente demande de révision est irrecevable dans ces conditions. En effet, soit elle a été déposée tardivement, en violation de l'art. 124 al. 1 let. d LTF, soit elle repose sur des faits ou moyens de preuve qui n'ont pas été découverts "après coup", au sens de l'<ref-law>.
5. Le requérant, qui succombe, devra payer les frais de la procédure fédérale (<ref-law>) et verser des dépens à l'intimée (art. 68 al. 1 et 2 LTF). L'indemnité allouée de ce chef sera prélevée sur les sûretés fournies par le requérant.

Par ces motifs, le Tribunal fédéral prononce:
1. La demande de révision est irrecevable.
2. Les frais judiciaires, arrêtés à 85'000 fr., sont mis à la charge du requérant.
3. Le requérant versera à l'intimée une indemnité de 150'000 fr. à titre de dépens; cette indemnité sera prélevée sur les sûretés déposées à la Caisse du Tribunal fédéral.
4. Le présent arrêt est communiqué aux mandataires des parties et au président du Tribunal arbitral.
Lausanne, le 23 juillet 2012
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Carruzzo