Sachverhalt:
A. A.a X._, Tschechische Republik, (Beschwerdeführer) investiert unter anderem in grosse Unternehmen der tschechischen Stahl- und Maschinenindustrie.
Y._, Tschechische Republik (Beschwerdegegner) beherrscht die niederländische Holdinggesellschaft AY._ Holding B.V. (vormals AAY._ Group Holding B.V..), die unter anderem an zahlreichen tschechischen Unternehmen beteiligt ist.
A.b Am 9. November 2005 schloss der Beschwerdeführer mit dem Beschwerdegegner einen "Vertrag über Gemeinsames Vorgehen" ab. Mit Kaufvertrag vom gleichen Tag zwischen dem Beschwerdeführer und der AY._ Holding B.V. verpflichtete sich der Beschwerdeführer, seinen Aktienanteil von 45 % der Gesellschaft A._ Holding an die AY._ Holding B.V. zu übertragen. Dem Beschwerdeführer sollte durch Zeichnung der anlässlich einer Kapitalerhöhung neu ausgegebenen Aktien der AY._ Holding B.V. sowie unter Verrechnung der Liberierungsforderung mit dem Kaufpreisanspruch des Beschwerdeführers eine 50 %-Beteiligung an der AY._ Holding B.V. verschafft werden. Der "Vertrag über Gemeinsames Vorgehen" sah für den Fall der Nichterfüllung bestimmter Vertragspflichten eine Konventionalstrafe vor. Beide Verträge enthalten zudem eine Rechtswahlklausel zugunsten des tschechischen Rechts sowie eine Schiedsklausel.
Die Kapitalerhöhung kam in der Folge nicht zustande und die Übertragung der Aktien der Gesellschaft A._ Holding blieb ebenfalls aus.
B. B.a Die AY._ Holding B.V. erhob mit Eingabe vom 9. November 2006 bei der Internationalen Handelskammer (ICC) Schiedsklage gegen den Beschwerdeführer und verlangte gestützt auf den Aktienkaufvertrag vom 9. November 2005 die Übertragung der von ihm gehaltenen Aktien der A._ Holding (Verfahren ICC Nr. _). Das Schiedsgericht hiess die Klage gut.
Der Beschwerdeführer erhob gestützt auf den "Vertrag über Gemeinsames Vorgehen" vom 9. November 2005 seinerseits Schiedsklage gegen den Beschwerdegegner auf Zahlung der Konventionalstrafe (Verfahren ICC Nr. _). Dieser verlangte widerklageweise ebenfalls die Zahlung der Konventionalstrafe. Das Schiedsgericht wies die Klage des Beschwerdeführers ab; die Widerklage des Beschwerdegegners hiess es gut und verurteilte den Beschwerdeführer zur Zahlung von CZK 1'182'500'000.-- (entsprechend knapp Fr. 67 Mio.) zuzüglich Verzugszins.
Die beiden Verfahren wurden von denselben Schiedsrichtern beurteilt. Der Beschwerdeführer nominierte jeweils Q._, der Beschwerdegegner bzw. die AY._ Holding B.V. nominierten P._ als Schiedsrichter; diese einigten sich auf O._ als Obmann. Auf eine Vereinigung der beiden Verfahren verzichtete das Schiedsgericht.
C. Mit (innert Frist ergänzter) Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Schiedsentscheid vom 15. Mai 2009 in der Schiedssache ICC Nr. _ aufzuheben.
Der Beschwerdegegner beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Obmann des Schiedsgerichts hat sich in zwei Eingaben geäussert und beantragt sinngemäss ebenfalls die Abweisung der Beschwerde, soweit darauf eingetreten werden könne.
Der Beschwerdeführer reichte dem Bundesgericht eine Replik, der Beschwerdegegner eine Duplik ein. Der Beschwerdeführer nahm in einer weiteren Eingabe zur Duplik Stellung; der Beschwerdegegner wiederum äusserte sich dazu in einer kurzen Eingabe. Der Beschwerdegegner reichte dem Bundesgericht sodann ein "Gesuch um Beschleunigung des Verfahrens" ein.
D. Mit Verfügung des Bundesgerichts vom 24. Juli 2009 wurde das Gesuch des Beschwerdeführers um aufschiebende Wirkung abgewiesen.

Erwägungen:
1. 1.1 Das vom Beschwerdegegner eingereichte "Gesuch um Beschleunigung des Verfahrens" wird mit dem Entscheid in der Sache gegenstandslos.
1.2 Der Beschwerdeführer beantragt, es sei das vorliegende Verfahren aufgrund der Identität der Rüge der vorschriftswidrigen Zusammensetzung des Schiedsgerichts mit dem Beschwerdeverfahren 4A_256/2009 zu vereinigen. Grundsätzlich besteht die Möglichkeit der Vereinigung verschiedener bundesgerichtlicher Verfahren (vgl. <ref-ruling> E. 1a S. 385; <ref-ruling> E. 1 S. 272). Die beiden vom Beschwerdeführer erhobenen Beschwerden richten sich jedoch gegen Entscheide, die im Rahmen zweier Schiedsverfahren ergangen sind, in denen der Beschwerdeführer jeweils verschiedenen Parteien gegenüberstand und unterschiedliche Ansprüche zu beurteilen waren. Zwar erhebt er in beiden Verfahren aufgrund der identischen Zusammensetzung der Schiedsgerichte im Wesentlichen die gleiche Rüge der fehlenden Unabhängigkeit zweier Schiedsrichter (<ref-law>), den übrigen Rügen liegen aber unterschiedliche tatsächliche und rechtliche Verhältnisse zugrunde. Eine Vereinigung der beiden Verfahren drängt sich vorliegend nicht auf.
2. Die Beschwerde in Zivilsachen ist gegen Entscheide von Schiedsgerichten unter den Voraussetzungen der Art. 190-192 IPRG zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Zürich. Die Parteien haben ihren Sitz nicht in der Schweiz. Da sie die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
2.2 Der Beschwerdegegner macht zu Unrecht geltend, auf die Beschwerde könne nicht eingetreten werden, weil die Parteien in der Schiedsvereinbarung auf die Erhebung von Rechtsmitteln gegen den Schiedsentscheid verzichtet hätten.
Hat keine der Parteien Wohnsitz, gewöhnlichen Aufenthalt oder eine Niederlassung in der Schweiz, wie dies vorliegend der Fall ist, so können sie zwar nach <ref-law> die Anfechtung der Schiedsentscheide durch eine ausdrückliche Erklärung in der Schiedsvereinbarung oder in einer späteren Übereinkunft vollständig ausschliessen. Nach der Rechtsprechung des Bundesgerichts muss aus der Erklärung jedoch der gemeinsame Wille der Parteien unmissverständlich hervorgehen, von der Möglichkeit im Sinne von <ref-law> Gebrauch zu machen und auf die Anfechtung des internationalen Schiedsentscheids beim Bundesgericht zu verzichten. Ob es sich so verhält, ist durch Auslegung der konkreten Schiedsklausel zu ermitteln (vgl. <ref-ruling> E. 4.3.1 S. 240 f.; <ref-ruling> E. 4.2, insb. E. 4.2.3.1 S. 177 ff.; je mit Hinweisen).
Nach dem Wortlaut der zu beurteilenden Schiedsklausel werden Streitigkeiten aus dem Vertrag "unter Ausschluss der Zuständigkeit der allgemeinen Gerichte und endgültig gemäss den Regeln des Schiedsgerichts der Internationalen Handelskammer" entschieden. Dies genügt entgegen der Ansicht des Beschwerdegegners den Anforderungen an einen ausdrücklichen Verzicht im Sinne von <ref-law> nicht. Zum einen wird mit dem Hinweis auf den Ausschluss der Zuständigkeit der "allgemeinen Gerichte" lediglich zum Ausdruck gebracht, dass ein Schiedsgericht anstelle der staatlichen Gerichte über allfällige Streitigkeiten entscheiden soll. Ein Wille der Vertragsparteien, auf die Anfechtung des Schiedsentscheids beim Bundesgericht zu verzichten, lässt sich daraus nicht ableiten. Zum anderen schliesst die Bezeichnung eines Entscheids als "endgültig" nach allgemeinem Sprachgebrauch im Zivilprozessrecht einen Weiterzug mit ausserordentlichen Rechtsmitteln nicht aus, sondern lediglich die (freie) Prüfung des Entscheids mittels ordentlicher Rechtsmittel, wie beispielsweise einer Berufung (vgl. die Urteile 4A_224/2008 vom 10. Oktober 2008 E. 2.6.3; 4P.114/2006 vom 7. September 2006 E. 5.3; je mit Hinweisen). So bestimmt denn auch <ref-law> in Absatz 1, dass der Entscheid des Schiedsgerichts "endgültig" sei, sieht aber in den folgenden beiden Absätzen 2 und 3 in Verbindung mit <ref-law> eine Anfechtungsmöglichkeit aus abschliessend aufgezählten Gründen beim Bundesgericht als einziger Beschwerdeinstanz mit dem Rechtsmittel der Beschwerde in Zivilsachen nach <ref-law> vor.
2.3 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
2.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von Art. 97 sowie Art. 105 Abs. 2 BGG ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733; je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
3. Der Beschwerdeführer rügt unter Berufung auf <ref-law>, das Schiedsgericht sei vorschriftswidrig zusammengesetzt gewesen. Er bringt vor, der vom Beschwerdegegner nominierte P._ sowie der Vorsitzende des Schiedsgerichts, O._, seien befangen gewesen, weshalb keine Gewähr für ein unparteiliches und unabhängiges Schiedsgericht bestanden habe.
3. Der Beschwerdeführer rügt unter Berufung auf <ref-law>, das Schiedsgericht sei vorschriftswidrig zusammengesetzt gewesen. Er bringt vor, der vom Beschwerdegegner nominierte P._ sowie der Vorsitzende des Schiedsgerichts, O._, seien befangen gewesen, weshalb keine Gewähr für ein unparteiliches und unabhängiges Schiedsgericht bestanden habe.
3.1 3.1.1 Der Beschwerdeführer habe Ende Mai 2007 aus den tschechischen Medien erfahren, dass die ICC P._ in einem anderen Schiedsverfahren (gegen Z._), bei dem dieser - wie im Verfahren ICC Nr. _ - ebenfalls von der AY._ Holding B.V. nominiert worden sei, nicht bestätigt habe, weil er zu häufig vom Beschwerdegegner oder von mit diesem verbundenen Personen nominiert worden sei. Im genannten Zeitungsartikel sei "davon die Rede, dass JUDr. P._ von Y._ bzw. von mit ihm verbundenen Personen in letzter Zeit in ca. 10 verschiedenen Schiedsverfahren als Schiedsrichter nominiert worden sei". Dies könne der Beschwerdeführer aus eigener Anschauung bestätigen, da er dem Beschwerdegegner im Jahr 2006 auch in zwei Verfahren vor dem Schiedsgericht bei der Wirtschaftskammer der Tschechischen Republik gegenübergestanden sei. Auch dort habe P._ als ernannter Parteischiedsrichter auf Seiten des Beschwerdegegners gestanden und sei daher im Laufe der Zeit zu dessen "Hausschiedsrichter" geworden. Dennoch habe die ICC P._ im vorliegenden Schiedsverfahren am 27. April 2007 bestätigt und auch den Ablehnungsantrag des Beschwerdeführers mit Entscheid vom 28. September 2007, wie üblich ohne Begründung, abgewiesen.
3.1.2 Gegen einen Ablehnungsentscheid eines privaten Gremiums wie dem Internationalen Schiedsgerichtshof der ICC ist ein direkter Rechtsbehelf ausgeschlossen; ein solcher Entscheid ist jedoch einer indirekten Überprüfung im Rahmen eines Beschwerdeverfahrens gegen den Schiedsspruch selbst zugänglich (<ref-ruling> E. 2.2 S. 332; <ref-ruling> E. 3b S. 360 f.). Der Beschwerdeführer zeigt allerdings, soweit seine Vorbringen überhaupt genügend substantiiert sind, keine Umstände auf, die Anlass zu berechtigten Zweifeln an der Unabhängigkeit von P._ (vgl. <ref-law>) geben würden.
Zunächst ist die einzig gestützt auf einen Zeitungsartikel vom 20. Mai 2007 erhobene Behauptung, P._ sei "in letzter Zeit" in zahlreichen Fällen des Beschwerdegegners bzw. "von mit diesem verbundenen Personen" als Schiedsrichter nominiert worden, zu unbestimmt, als dass deren Wahrheitsgehalt anhand eines Beweisverfahrens geklärt und gestützt darauf die Unabhängigkeit des fraglichen Schiedsrichters beurteilt werden könnte. Der Beschwerdeführer hätte zumindest die verschiedenen Schiedsverfahren unter Angabe der zeitlichen Abfolge sowie der daran beteiligten Schiedsparteien konkret benennen und aufzeigen müssen, welche Partei P._ ernannt hat und in welcher Beziehung diese zum Beschwerdegegner steht. Der blosse Umstand, dass P._ in einem anderen ICC Schiedsverfahren zwischen der AY._ Holding B.V. und einem Herrn Z._ (ICC Nr. _) vom Internationalen Schiedsgerichtshof der ICC die Bestätigung versagt wurde, lässt zudem keine Rückschlüsse auf die Frage der Unabhängigkeit im vorliegenden Verfahren zu. Entgegen der in der Beschwerde erhobenen Behauptung ergibt sich aus dem Schreiben der ICC vom 27. April 2007 in der Sache ICC Nr. _ nicht, dass die Bestätigung aufgrund einer "engen Verflechtung" mit dem Beschwerdegegner bzw. der AY._ Holding B.V. verweigert worden wäre.
An den beiden in der Beschwerde erwähnten Verfahren vor dem Schiedsgericht bei der Wirtschaftskammer der Tschechischen Republik im Jahr 2006 war der Beschwerdeführer nach eigenen Angaben selbst als Partei beteiligt. Er hatte demnach Kenntnis davon, dass P._ in diesen Schiedsverfahren vom Beschwerdegegner nominiert worden war, als P._ am 27. April 2007 im vorliegenden Verfahren vom Schiedsgerichtshof der ICC als Schiedsrichter bestätigt wurde. Hätte er sich auf den Umstand berufen wollen, dass P._ in den letzten drei Jahren bereits mindestens zweimal als Schiedsrichter durch die Gegenpartei bzw. eine verbundene Person nominiert worden wäre, so hätte er dies unverzüglich nach dessen Bestätigung vorbringen müssen und mit seinem Ablehnungsbegehren nicht bis zum 17. August 2007 zuwarten dürfen (vgl. <ref-law>). Der Beschwerdeführer hat seinen Anspruch auf spätere Anrufung des Ablehnungsgrunds daher verwirkt (vgl. <ref-ruling> E. 3.1 S. 449; <ref-ruling> E. 3c S. 253 f.; je mit Hinweisen).
Es braucht unter diesen Umständen nicht darauf eingegangen zu werden, wie es sich mit dem Argument des Beschwerdeführers verhält, gemäss Ziffer 3.1.3 der Richtlinien der International Bar Association (IBA Guidelines on Conflicts of Interest in International Arbitration, genehmigt am 22. Mai 2004; <http://www.ibanet.org>, unter Publications/IBA guides and free materials [besucht am 3. März 2010]) könne ein Schiedsrichter, der in den letzten drei Jahren mehr als zweimal von der gleichen Partei als Schiedsrichter ernannt wurde, nur dann amten, wenn er diese Tatsache offengelegt habe und die Parteien gegen sein Wirken keine Einwände erhoben hätten. Im Übrigen verweist der Beschwerdeführer auf Ziffer 2.3.6 der erwähnten IBA Guidelines, wonach eine bedeutende wirtschaftliche Beziehung der Anwaltskanzlei des Schiedsrichters zu einer Partei oder einer mit dieser verbundenen Person einen Interessenkonflikt darstelle und der Schiedsrichter nur amten könne, wenn die Parteien sich im Wissen um diesen Umstand ausdrücklich mit dessen Mitwirkung einverstanden erklärt hätten. Er zeigt jedoch nicht konkret auf, worin im zu beurteilenden Fall eine derartige bedeutende wirtschaftliche Beziehung bestehen soll.
Die Rüge, der vom Beschwerdegegner nominierte Schiedsrichter P._ sei befangen gewesen bzw. es habe der Anschein der Voreingenommenheit bestanden, geht fehl.
Die Rüge, der vom Beschwerdegegner nominierte Schiedsrichter P._ sei befangen gewesen bzw. es habe der Anschein der Voreingenommenheit bestanden, geht fehl.
3.2 3.2.1 Die angebliche Befangenheit des Obmanns O._ begründet der Beschwerdeführer mit Umständen, von denen er Ende Oktober 2008 anlässlich eines Schiedsverfahrens in London zwischen einer von ihm errichteten Stiftung und der Gesellschaft B._ Limited erfahren habe. So seien die Eigentümer der B._ Limited, die Herren S._ und T._, gleichzeitig Mehrheitsaktionäre und Verwaltungsräte der slowakischen Gesellschaft C._ a.s. mit Sitz in Bratislava. Der Schiedsobmann O._ sei ebenfalls im Verwaltungsrat der C._ a.s. und sitze zudem mit denselben Personen zusammen im Verwaltungsrat einer weiteren Gesellschaft, der D._ a.s. (Bratislava).
Der Beschwerdeführer bringt weiter vor, er habe weitere Nachforschungen angestellt, nachdem er über diese seltsame "Connection" misstrauisch geworden sei. Er habe dabei erfahren müssen, dass dieselbe C._ s.a. mit dem Beschwerdegegner bzw. von diesem beherrschten Gesellschaften offenbar regelmässig zusammenarbeite. So sei die Gesellschaft in die Schaffung der AY._ Holding B.V. eingebunden gewesen, indem sie für diese Aktien der tschechischen Industriegesellschaft E._ gehalten und ihr diese im Jahr 2005 verkauft habe.
Noch enger sei die Zusammenarbeit zwischen der C._ a.s. und dem Beschwerdegegner im Prozess um Forderungen der in den 90er-Jahren in Konkurs gefallenen Bank F._ a.s. gegenüber einer zweiten tschechischen Grossbank, G._ a.s., gewesen: So habe die C._ a.s. im März 2005 mit der niederländischen Gesellschaft H._ B.V. ein sogenanntes "Consignment Agreement" abgeschlossen, wonach die I._ a.s. in eigenem Namen, aber auf Rechnung der H._ B.V. eine Forderung in Höhe von CZK 40 Milliarden gegen die Grossbank G._ a.s. schiedsgerichtlich durchsetzen sollte. In dem in der Folge eingeleiteten Verfahren ICC Nr. _ habe P._ als Obmann geamtet. Die Anwaltskanzlei der I._ a.s. in diesem Verfahren, J._, vertrete in Tschechien regelmässig auch die Interessen des Beschwerdegegners und der mit ihm verbundenen Personen. Dem Anhang eines E-Mails dieser Kanzlei vom 17. März 2006 lasse sich der Entwurf einer Vollmacht der H._ B.V. zur Geltendmachung der Forderung gegenüber der Grossbank G._ a.s. im Verfahren ICC Nr. _ entnehmen. Im E-Mail schreibe eine Frau K._ hierzu, dass man sich der C._ a.s. aus Kostengründen eventuell entledigen wolle und der Beschwerdegegner bzw. seine BY._ Group a.s. "es selber machen werde", womit die Geltendmachung der Forderung gemeint sei. Daraus ergebe sich, so der Beschwerdeführer, dass zwischen der C._ a.s. und Gesellschaften und Vertretern des Beschwerdegegners enge wirtschaftliche Verflechtungen bestünden. Der Wortwahl des E-Mails nach zu schliessen ("get rid of C._"), sei sogar von einem (mittelbaren) Beherrschungsverhältnis zwischen der BY._ Group a.s. und der C._ a.s. auszugehen.
Die Behauptungen des Beschwerdeführers, mit denen er seinen Vorwurf der Befangenheit begründet, werden vom Beschwerdegegner bestritten.
3.2.2 Der Beschwerdeführer zeigt mit seinen Ausführungen keine Beziehung des Schiedsobmanns O._ zum Beschwerdegegner auf, die bei objektiver Betrachtung den Anschein der Befangenheit und die Gefahr der Voreingenommenheit begründen würde.
Abgesehen davon, dass aus den Ausführungen des Beschwerdeführers nicht hervorgeht, dass er den von ihm behaupteten Ablehnungsgrund dem Schiedsgericht sowie dem Beschwerdegegner unverzüglich mitgeteilt hätte (vgl. <ref-law>), legt er insbesondere nicht substantiiert dar, inwiefern das Verhältnis der C._ a.s. mit dem Beschwerdegegner derart sein soll, dass der Einsitz des Obmanns O._ im Verwaltungsrat der genannten Gesellschaft im vorliegenden Verfahren den Anschein der Befangenheit erwecken würde. Die vom Beschwerdeführer geschilderte Zusammenarbeit lässt nicht auf ein Verhältnis schliessen, das über gewöhnliche Geschäftsbeziehungen hinausgehen würde. Die Behauptung, die C._ a.s. werde vom Beschwerdegegner bzw. mit diesem verbundenen Personen beherrscht, ist spekulativ und wird vom Beschwerdeführer nicht hinreichend begründet. Entgegen seiner Ansicht lässt sich dem E-Mail der Anwaltskanzlei J._ vom 17. März 2006 kein Hinweis auf ein solches Beherrschungsverhältnis entnehmen. Die darin geäusserte Absicht der BY._ Group a.s., auf die Dienste der C._ a.s. aus Kostengründen zu verzichten und die erwähnte Forderung selbst geltend zu machen, weist nicht auf ein unmittelbares oder mittelbares Beherrschungsverhältnis hin.
Im Übrigen begründet weder der Umstand, dass sich die I._ a.s. in einem Schiedsverfahren von einer Anwaltskanzlei vertreten liess, die in Tschechien regelmässig auch die Interessen des Beschwerdegegners und der mit ihm verbundenen Personen vertreten soll, noch die Tatsache, dass in besagtem Schiedsverfahren P._ als Obmann amtete, die Gefahr der Voreingenommenheit von O._ im vorliegenden Verfahren. Ebenso wenig gibt der blosse Umstand, dass O._ gemeinsam mit Personen im Verwaltungsrat einer Gesellschaft sass, die mit der B._ Limited eine Gesellschaft beherrschen sollen, die ihrerseits in einem Schiedsverfahren als Partei einer angeblich vom Beschwerdeführer errichteten Stiftung gegenüberstand, Anlass zu berechtigten Zweifeln an der Unabhängigkeit dieses Schiedsrichters im vorliegenden Verfahren.
Entgegen der in der Beschwerde geäusserten Ansicht kann nicht davon ausgegangen werden, dass aufgrund der geschilderten Verhältnisse eine gegenseitige Rücksichtnahme der beiden Schiedsrichter P._ und O._ sowie die "wohlwollende Berücksichtigung" der Interessen des Beschwerdegegners "vorprogrammiert" seien. Die vom Beschwerdeführer vorgebrachten Behauptungen reichen nicht aus, um einen Anschein der Befangenheit (vgl. <ref-law>) zu erwecken.
4. Der Beschwerdeführer wirft der Vorinstanz eine Verletzung des Ordre public (<ref-law>) vor.
4.1 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). Gegen den Ordre public verstösst die materielle Beurteilung eines streitigen Anspruchs nur, wenn sie fundamentale Rechtsgrundsätze verkennt und daher mit der wesentlichen, weitgehend anerkannten Wertordnung schlechthin unvereinbar ist, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte. Zu diesen Prinzipien gehören die Vertragstreue (pacta sunt servanda), das Rechtsmissbrauchsverbot, der Grundsatz von Treu und Glauben, das Verbot der entschädigungslosen Enteignung, das Diskriminierungsverbot und der Schutz von Handlungsunfähigen. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 2.2 S. 392 ff.; <ref-ruling> E. 6b S. 198; <ref-ruling> E. 6a S. 166 f.).
4.1 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). Gegen den Ordre public verstösst die materielle Beurteilung eines streitigen Anspruchs nur, wenn sie fundamentale Rechtsgrundsätze verkennt und daher mit der wesentlichen, weitgehend anerkannten Wertordnung schlechthin unvereinbar ist, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte. Zu diesen Prinzipien gehören die Vertragstreue (pacta sunt servanda), das Rechtsmissbrauchsverbot, der Grundsatz von Treu und Glauben, das Verbot der entschädigungslosen Enteignung, das Diskriminierungsverbot und der Schutz von Handlungsunfähigen. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 2.2 S. 392 ff.; <ref-ruling> E. 6b S. 198; <ref-ruling> E. 6a S. 166 f.).
4.2 4.2.1 Nicht einzugehen ist auf den unter dem Titel der Verletzung des Ordre public wiederum pauschal erhobenen Vorwurf der Befangenheit zweier Schiedsrichter. Auch mit dem Vorbringen, der dritte Schiedsrichter, Q._, habe den angefochtenen Schiedsentscheid nicht mitunterzeichnet, erhebt der Beschwerdeführer keine hinreichend begründete Rüge (Art. 77 Abs. 3 i.V.m. <ref-law>).
4.2.2 Der Grundsatz der Vertragstreue ist nur dann verletzt, wenn das Schiedsgericht zwar die Existenz eines Vertrags bejaht, die daraus sich ergebenden Konsequenzen jedoch missachtet, oder - umgekehrt - die Existenz eines Vertrags verneint, jedoch trotzdem eine vertragliche Verpflichtung bejaht (Urteile 4A_370/2007 vom 21. Februar 2008 E. 5.5; 4P.104/2004 vom 18. Oktober 2004 E. 6.3; vgl. auch BGE <ref-ruling> E. 6c/cc S. 171; <ref-ruling> E. 4b S. 638).
Der Beschwerdeführer legt nicht dar, inwiefern sich der angefochtene Schiedsspruch über diesen Grundsatz hinweggesetzt hätte. Er beanstandet vielmehr die Auslegung des mit dem Beschwerdegegner abgeschlossenen "Vertrags über Gemeinsames Vorgehen" vom 9. November 2005 sowie die schiedsgerichtliche Beurteilung der Voraussetzungen der darin vorgesehenen Konventionalstrafe. Er kritisiert verschiedene Feststellungen der Vorinstanz als unhaltbar und zieht gestützt darauf vom angefochtenen Schiedsspruch abweichende Schlüsse. Der Beschwerdeführer setzt sich mit seinen Vorbringen, ohne eine zureichende Sachverhaltsrüge (vgl. vorn E. 2.4) zu erheben, über die für das Bundesgericht verbindlichen Sachverhaltsfeststellungen des Schiedsgerichts hinweg und verkennt gleichzeitig, dass eine falsche Vertragsauslegung für einen Verstoss gegen den Ordre public nicht ausreicht (BGE <ref-ruling> E. 4b S. 638; Urteile 4P.104/2004 vom 18. Oktober 2004 E. 6.3; 4P.62/1999 vom 26. Mai 1999 E. 1a/aa a.E.). Der Beschwerdeführer macht keine Missachtung des Grundsatzes der Vertragstreue geltend, wenn er die Bedingungen für die geschuldete Konventionalstrafe entgegen dem angefochtenen Entscheid als nicht erfüllt erachtet.
4.2.3 Die Vorbringen in der Beschwerdeergänzung vermögen den Vorwurf des Rechtsmissbrauchs nicht zu begründen. Da im vorliegenden Verfahren die im "Vertrag über Gemeinsames Vorgehen" vorgesehene Konventionalstrafe zu beurteilen war und nicht allfällige Ansprüche aus dem Aktienkaufvertrag zwischen dem Beschwerdeführer und der AY._ Holding B.V., zeigt der Beschwerdeführer mit den angeblich widersprüchlichen prozessualen Vorbringen der Gegenpartei zur Frage der selbständigen Erfüllbarkeit des Aktienkaufvertrags nicht auf, inwiefern der angefochtene Entscheid im Ergebnis dem Ordre public widersprechen soll.
Entsprechendes gilt für den in der Beschwerdeergänzung erhobenen Vorwurf der culpa in contrahendo im Zusammenhang mit der Frage, wer als erster seine Verpflichtungen aus den abgeschlossenen Vereinbarungen verletzt habe. Das Schiedsgericht hielt dafür, dass die vom Beschwerdeführer am 9. November 2005 ausgestellte Vollmacht den Anforderungen nach Artikel 2.2 des "Vertrags über Gemeinsames Vorgehen" nicht genügte. Gestützt auf die Erwägung, dass der Beschwerdeführer bis zum 31. Dezember 2005 keine rechtsgenügliche Vollmacht für die Kapitalerhöhung der AY._ Holding B.V. ausgestellt habe, erachtete das Schiedsgericht die Voraussetzungen der in Artikel 2.2 vorgesehenen Konventionalstrafe als erfüllt. Indem der Beschwerdeführer entgegen dem angefochtenen Entscheid vorbringt, der Beschwerdegegner hätte ihn rechtzeitig auf die Mängel der Vollmacht hinweisen müssen und eine eigene Pflichtverletzung bestreitet, kritisiert er einmal mehr die Vertragsauslegung durch die Vorinstanz, ohne eine Ordre public-Widrigkeit darzutun.
Eine Verletzung des Prinzips der Vertragstreue (pacta sunt servanda), des Rechtsmissbrauchsverbots bzw. des Grundsatzes von Treu und Glauben ist nicht dargetan.
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 75'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 85'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem ICC Schiedsgericht mit Sitz in Zürich schriftlich mitgeteilt.
Lausanne, 11. Januar 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann