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. 