Sachverhalt: A. A.a A._ (Beschwerdeführer) mit Wohnsitz in D._ ist professioneller Eishockeyspieler. Er nahm mit der deutschen Eishockey-Nationalmannschaft an verschiedenen internationalen Wettkämpfen teil, so unter anderem an den Eishockey-Weltmeisterschaften in den Jahren 2003, 2004, 2006, 2007 und 2008 sowie an den Olympischen Winterspielen in Turin im Jahr 2006. Die Welt-Anti-Doping-Agentur (WADA) (Beschwerdegegnerin) ist eine Stiftung schweizerischen Rechts mit Sitz in Lausanne. Ihr Zweck ist der weltweite Kampf gegen Doping im Sport. Die International Ice Hockey Federation (IIHF) ist der internationale Eishockeyverband mit Sitz in Zürich. A.b Am 6. März 2008 um 12.30 Uhr erschien Herr B._ im Auftrag der deutschen Nationalen Anti-Doping-Agentur (NADA) am Wohnsitz des Beschwerdeführers, um eine unangemeldete Probe ("out-of-competition sample collection"; "Trainingsprobe") vorzunehmen. Nach Darstellung der Beschwerdegegnerin weigerte sich der Beschwerdeführer, auch nachdem er vom Dopingkontrolleur auf die schwerwiegenden disziplinarischen Sanktionen hingewiesen worden sei, die Kontrolle durchzuführen. Unstreitig ist, dass der Dopingkontrolleur die Wohnung des Beschwerdeführers um 12.50 Uhr unverrichteter Dinge verliess. Vier Minuten später meldete sich der Beschwerdeführer telefonisch bei der NADA und informierte sie über den Vorfall. Um 14.16 Uhr rief er nochmals bei der NADA an und erklärte, er wolle sich einer Probenahme unterziehen, worauf ihm die NADA mitteilte, eine Wiederholung der Kontrolle sei nicht möglich. In der Folge fand auf seine Initiative hin noch am gleichen Tag um 17.00 Uhr eine Dopingkontrolle statt, die vom Deutschen Eishockey-Bund (DEB) organisiert und von Herrn B._ durchgeführt wurde. Die Probe wurde vom Institut für Dopinganalytik und Sportbiochemie Dresden analysiert; dabei liessen sich keine verbotenen Wirkstoffe oder unzulässigen Methoden nachweisen. A.c Am 7. März 2008 informierte die NADA den Deutschen Eishockey-Bund über den Vorfall. Am 19. März 2008 teilte dieser der NADA seine Absicht mit, den Beschwerdeführer öffentlich zu verwarnen. Die NADA wiederum wies den DEB darauf hin, dass die Verweigerung einer Probenahme einen Verstoss gegen Artikel 2.3 des NADA Code (NADC) bedeute, der mit Artikel 2.3 des WADA Code (WADC) übereinstimmt, und entsprechend zu sanktionieren sei. Der DEB informierte die NADA, dass die im NADC bzw. WADC vorgesehenen Sanktionen übermässig seien und angesichts der Umstände des konkreten Falls eine öffentliche Verwarnung ausreiche. Entsprechend sprach er am 15. April 2008 eine öffentliche Verwarnung gegen den Spieler aus und bestrafte ihn mit einer Busse von EUR 5'000.-- sowie 56 Stunden gemeinnützige Arbeit. NADA nahm vom Entscheid des DEB über die Medien Kenntnis und erfuhr dabei auch, dass die IIHF diesen unterstützte und den Spieler an der Eishockey-Weltmeisterschaft in Kanada vom 2. - 11. Mai 2008 würde spielen lassen. Die NADA informierte daher am 21. April 2008 die Beschwerdegegnerin, damit diese Massnahmen ergreifen konnte. Mit Schreiben vom 6. Mai 2008 ersuchte die Beschwerdegegnerin gestützt auf Artikel 3.1 der IIHF-Disziplinarordnung 2004 (Disciplinary Regulations) einerseits das Direktorium der IIHF-Weltmeisterschaften, den Beschwerdeführer ab 6. Mai 2008 einstweilig zu suspendieren und andererseits die IIHF, innert 48 Stunden einen Entscheid über die vorläufige Suspendierung zu fällen. Im Weiteren forderte die Beschwerdegegnerin die IIHF-Disziplinarkommission (Disciplinary Committee) auf, ein Disziplinarverfahren gegen den Beschwerdeführer einzuleiten und ihn mit einer zweijährigen Spielsperre zu belegen. Das Präsidium der IIHF teilte der Beschwerdegegnerin mit E-Mail vom 7. Mai 2008 mit, dass sie nicht in der Lage sei, dem Antrag entsprechend tätig zu werden. Die IIHF wies unter anderem darauf hin, dass die vom Deutschen Eishockey-Bund eingesetzte interne Disziplinarkommission am 15. April 2008 einen Entscheid in der Sache gefällt habe und die Rechtsmittelfrist noch laufe. Die Beschwerdegegnerin schrieb der IIHF gleichentags, sie gehe davon aus, dass es sich beim Schreiben vom 7. Mai 2008 um eine Entscheidung im Sinne der IIHF-Disziplinarordnung handle, die einem Weiterzug an das Tribunal Arbitral du Sport (TAS) unterliege. A.d Am 9. Mai 2008 focht die Beschwerdegegnerin den Entscheid des DEB vom 15. April 2008 beim Ad-hoc-Schiedsgericht des Deutschen Olympischen Sportbundes an und beantragte, der Entscheid sei aufzuheben und es sei gegen den Spieler eine zweijährige Spielsperre zu verhängen. Das Ad-hoc-Schiedsgericht wies die Beschwerde mit Entscheid vom 3. Dezember 2008 ab, da es für die von der Beschwerdegegnerin beantragte Sanktion an einer rechtlichen Grundlage fehle. B. Am 27. Mai 2008 appellierte die Beschwerdegegnerin beim TAS gegen das Schreiben der IIHF vom 7. Mai 2008 und beantragte, es sei eine zweijährige Spielsperre zu verhängen (Verfahren CAS 2008/A/1564). Sie wies darauf hin, dass die Schiedsklage zur Wahrung ihrer Rechte erfolge, insbesondere für den Fall, dass die beim deutschen Ad-hoc-Schiedsgericht eingereichte Klage nicht zugelassen würde. Das Verfahren wurde daraufhin bis zum Entscheid des deutschen Schiedsgerichts sistiert. In der Folge focht die Beschwerdegegnerin auch den Entscheid des Ad-hoc-Schiedsgerichts des Deutschen Olympischen Sportbundes beim TAS an (Verfahren CAS 2008/A/1738). Das TAS trat darauf jedoch mit Entscheid vom 23. Juni 2009 mangels Zuständigkeit nicht ein. Die IIHF verzichtete auf eine Teilnahme am Schiedsverfahren. Der Beschwerdeführer erhob unter anderem die Einrede der Unzuständigkeit, da es an einer Schiedsvereinbarung fehle. C. Das TAS erachtete sich hinsichtlich des zuerst erhobenen Appeal (Verfahren CAS 2008/A/1564) gestützt auf das vom Beschwerdeführer jeweils im Hinblick auf die Weltmeisterschaft unterzeichnete "Player Entry Form" für zuständig und sah das E-Mail des IIHF vom 7. Mai 2008 als anfechtbaren Entscheid an. Es hob den Entscheid der IIHF mit Schiedsspruch vom 23. Juni 2009 auf und verhängte gegen den Beschwerdeführer eine zweijährige Spielsperre. D. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, der Schiedsspruch des TAS vom 23. Juni 2009 (Verfahren CAS 2008/A/1564) sei aufzuheben. Sowohl die Beschwerdegegnerin als auch die Vorinstanz schliessen auf Abweisung der Beschwerde. Der Beschwerdeführer hat dem Bundesgericht eine Replik eingereicht. E. Mit Verfügung vom 7. September 2009 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung erteilt.