Sachverhalt:
A. A.a Y._, (Beschwerdegegner) ist ein erfolgreicher Langstreckenläufer.
X._, (Beschwerdeführer) ist der nationale Leichtathletikverband von Z._ und als solcher Mitglied der International Association of Athletics Federations (IAAF).
A.b Am 12. März 2006 wurde der Beschwerdegegner anlässlich des Marathons in Seoul, Südkorea, einer Dopingkontrolle unterzogen. Die Probe des Beschwerdegegners wurde in eine A- sowie eine B-Probe aufgeteilt und an das Doping Center of the Korea Institute of Science and Technology in Seoul gesandt, dessen Labor von der Welt-Anti-Doping-Agentur (WADA) anerkannt ist. Am 16. März 2006 wurde die A-Probe von A._ untersucht und es wurde die verbotene Substanz 19-Norandrosteron nachgewiesen.
Am 13. April 2006 teilte die IAAF dem Beschwerdeführer das Testresultat mit und wies ihn an, nach Rule 37 der IAAF Competition Rules vorzugehen.
Am 17. April 2006 teilte der Beschwerdeführer dem Beschwerdegegner das positive Testresultat mit und informierte ihn über sein Recht zur Prüfung der B-Probe.
Der Beschwerdegegner bot keine Erklärung für den Nachweis von 19-Norandrosteron in seiner A-Probe an. Am 25. April 2006 wurde er vom Beschwerdeführer einstweilig für sämtliche Wettkämpfe gesperrt.
Am 16. Mai 2006 wurde die B-Probe von A._ unter Aufsicht von Dr. B._ untersucht. Wiederum liess sich die Substanz 19-Norandrosteron nachweisen.
B. B.a Am 10. September 2006 führte der Beschwerdeführer im Rahmen des Disziplinarverfahrens die erste Anhörung durch. Nach zahlreichen Verschiebungen fand am 11. Dezember 2008 eine weitere Anhörung vor einer neu zusammengesetzten Disziplinarkommission statt.
Mit Schreiben vom 11. Dezember 2008 teilte der Beschwerdeführer dem Beschwerdegegner mit, dass die Disziplinarkommission einstimmig ein Dopingvergehen festgestellt und für den Zeitraum vom 25. April 2006 bis 11. Dezember 2008 eine Sperre ausgesprochen habe. Dabei wurden dem Beschwerdegegner sämtliche anlässlich der Teilnahme am Seoul Marathon 2006 erlangten Preise und Einnahmen aberkannt.
B.b Der Beschwerdegegner focht den Entscheid der Disziplinarkommission des Beschwerdeführers vom 11. Dezember 2008 mit Eingabe vom 7. Januar 2009 beim Tribunal Arbitral du Sport (TAS) an. Er behauptete im Wesentlichen eine Verletzung von Art. 5.2.4.3.2.2 des "WADA Code International Standard for Laboratories", weil sowohl die A-Probe als auch die B-Probe von derselben Person (A._) durchgeführt worden war. Der Beschwerdeführer bestritt insbesondere die Zuständigkeit des TAS, da weder die Statuten noch die anderen anwendbaren Verbandsregeln eine Weiterzugsmöglichkeit an das TAS vorsähen.
Das TAS erwog, dass seine Zuständigkeit nicht auf die Verbandsregeln des Beschwerdeführers gestützt werden könne. Es erklärte sich jedoch gestützt auf ein von Dr. C._, dem IAAF Anti-Doping Administrator, verfasstes und an den Rechtsvertreter des Beschwerdegegners gerichtetes Schreiben vom 10. April 2008 dennoch für zuständig. Mit Schiedsentscheid vom 24. Juli 2009 hiess das TAS die Berufung des Beschwerdegegners gut, es hob den Entscheid des Beschwerdeführers vom 11. Dezember 2008 auf und liess den Beschwerdegegner ohne weitere Untersuchung wieder zur Teilnahme an Wettkämpfen zu.
C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Schiedsspruch des TAS vom 24. Juli 2009 aufzuheben und es sei festzustellen, dass das TAS zur Beurteilung der Berufung des Beschwerdegegners nicht zuständig sei. Eventualiter sei das Verfahren an die Vorinstanz zurückzuweisen.
Der Beschwerdegegner beantragt, es sei auf die Beschwerde nicht einzutreten, eventualiter sei diese abzuweisen. Das TAS schliesst auf Abweisung der Beschwerde.
Der Beschwerdeführer reichte dem Bundesgericht eine Replik, der Beschwerdegegner eine Duplik ein.
D. Mit Präsidialverfügung vom 16. November 2009 wurde das Gesuch des Beschwerdegegners um Sicherstellung einer allfälligen Parteientschädigung gutgeheissen. Der Beschwerdeführer überwies in der Folge den geforderten Betrag von Fr. 6'000.-- an die Bundesgerichtskasse.

Erwägungen:
1. Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel derjenigen des angefochtenen Entscheids. Wurde dieser Entscheid in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht verschiedener Sprachen bedienen, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde.
2. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Keine der Parteien hatte im relevanten Zeitpunkt ihren Sitz bzw. Wohnsitz in der Schweiz. Da die Parteien die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
2.2 Auf eine Beschwerde kann nur eingetreten werden, wenn der Beschwerdeführer ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (<ref-law>; dazu <ref-ruling> E. 1.1 S. 425 f.). Das Bundesgericht prüft grundsätzlich von Amtes wegen, ob auf eine Beschwerde eingetreten werden kann (<ref-law>). Immerhin ist die Beschwerde hinreichend zu begründen (Art. 42 Abs. 1 und 2 BGG), wobei der Beschwerdeführer auch darzulegen hat, dass die gesetzlichen Voraussetzungen des Beschwerderechts nach <ref-law> gegeben sind.
Der Beschwerdegegner bestreitet zu Unrecht ein aktuelles praktisches Rechtsschutzinteresse des Beschwerdeführers. Zwar endete die Sperre des Beschwerdegegners bereits am 11. Dezember 2008, dem Beschwerdegegner wurden jedoch auch sämtliche anlässlich des Seoul Marathons 2006 erlangten Preise und weiteren Vorteile aberkannt. Dem Beschwerdeführer kann, entgegen der in der Beschwerdeantwort geäusserten Ansicht, ein Interesse an der Durchsetzung der von ihm verhängten Sanktionen auch nicht mit dem Argument abgesprochen werden, das gewonnene Preisgeld von USD 80'000.-- sei nicht von ihm, sondern vom Marathonveranstalter geschuldet. Der Beschwerdeführer, dem als Nationalverband die Ahndung von Dopingverstössen obliegt, ist bezüglich der vom Beschwerdegegner am Seoul Marathon 2006 erlangten Preise nach wie vor an der Aufhebung des angefochtenen Entscheids interessiert.
Als haltlos erweist sich auch der mit teils spekulativen Behauptungen begründete Einwand des Beschwerdegegners, es fehle dem Beschwerdeführer an einem persönlichen Interesse an der Beschwerde, da er nicht für sich selbst, sondern auf Instruktion der IAAF handle. Der Umstand, dass den Beschwerdeführer als Mitglied der IAAF gewisse Pflichten im Zusammenhang mit Disziplinarverfahren treffen, deren Missachtung Sanktionen des internationalen Verbands nach sich ziehen können, lässt entgegen der Ansicht des Beschwerdegegners nicht auf ein fehlendes persönliches Interesse des Beschwerdeführers schliessen. Dieser ist nach <ref-law> zur Beschwerde berechtigt.
2.3 Dem Beschwerdegegner kann nicht gefolgt werden, wenn er vorbringt, auf die Beschwerde sei nicht einzutreten, weil sie nicht sämtliche Eventualbegründungen des angefochtenen Entscheids anfechte, so insbesondere nicht die Hauptbegründung, wonach der Beschwerdeführer das Berufungsverfahren an das TAS, wie im Schreiben der IAAF vom 10. April 2008 vorgeschlagen, akzeptiert habe.
Entgegen der in der Beschwerdeantwort vertretenen Ansicht handelt es sich dabei nicht um eine selbständige Begründung im Verhältnis zu den weiteren Erwägungen, der Beschwerdegegner habe das Schreiben vom 10. April 2008 als Offerte zum Abschluss einer Schiedsvereinbarung verstehen dürfen bzw. der Beschwerdeführer sei angesichts der Umstände ebenfalls an das Angebot der IAAF gebunden. Vielmehr setzt das Zustandekommen einer Schiedsvereinbarung zunächst eine Offerte zum Vertragsabschluss voraus, die das Schiedsgericht im Schreiben der IAAF erblickte. Sodann bedarf das Angebot einer Annahme seitens des Vertragspartners. Da es sich beim Schreiben vom 10. April 2008 nach Ansicht des TAS um eine Willenserklärung der IAAF handelte, hatte das Schiedsgericht schliesslich zu begründen, weshalb der Beschwerdeführer an die zwischen der IAAF und dem Beschwerdegegner zustande gekommene Vereinbarung gebunden sein soll. Eine selbständige Alternativbegründung zur Genehmigung der Vertretungshandlung der IAAF könnte höchstens in der Erwägung des angefochtenen Entscheids gesehen werden, wonach auch das Verhalten des Beschwerdeführers als Angebot zum Abschluss einer Schiedsvereinbarung zugunsten des TAS zu betrachten sei. Der angefochtene Entscheid ist in dieser Hinsicht jedoch keineswegs eindeutig und diese Lesart stünde in merkwürdigem Kontrast zur mehrfach wiederholten Darstellung des TAS, das Angebot sei von der IAAF ausgegangen sowie zu den ausgiebigen Ausführungen zur Frage der Genehmigung der Handlungen der IAAF bzw. deren Verbindlichkeit für den Beschwerdeführer, die sich nicht als Eventualbegründung verstehen lassen. Ohnehin richtet sich die Beschwerde gegen beide Begründungsansätze, weshalb nicht die Rede davon sein kann, es sei darauf wegen mangelnder Anfechtung verschiedener Eventualbegründungen nicht einzutreten.
2.4 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts betrifft, gilt davon allerdings, wie schon im Rahmen der altrechtlichen staatsrechtlichen Beschwerde, eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen kann (<ref-ruling> E. 1b S. 282; <ref-ruling> E. 4 S. 95 f.; Urteil 4A_240/2009 vom 16. Dezember 2009 E. 1.2). Der Hauptantrag des Beschwerdeführers ist insofern zulässig.
2.4 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts betrifft, gilt davon allerdings, wie schon im Rahmen der altrechtlichen staatsrechtlichen Beschwerde, eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen kann (<ref-ruling> E. 1b S. 282; <ref-ruling> E. 4 S. 95 f.; Urteil 4A_240/2009 vom 16. Dezember 2009 E. 1.2). Der Hauptantrag des Beschwerdeführers ist insofern zulässig.
2.5 2.5.1 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).
2.5.2 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. 105 Abs. 2 sowie Art. 97 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).
Der Beschwerdegegner behauptet zu Unrecht, es handle sich bei der Erwägung des TAS, der Beschwerdeführer habe den von der IAAF vorgeschlagenen Rechtsmittelweg akzeptiert, um eine tatsächliche Feststellung, die das Bundesgericht binde. Vielmehr hat das TAS die Zustimmung des Beschwerdeführers durchgehend in Anwendung des Vertrauensprinzips angenommen.
3. Der Beschwerdeführer macht unter Berufung auf <ref-law> geltend, die Vorinstanz habe sich zu Unrecht für zuständig erklärt.
3.1 Das TAS prüfte seine Zuständigkeit ausgehend von Artikel R47 des TAS-Code, wonach ein Entscheid eines Sportverbands beim TAS angefochten werden kann, sofern die Statuten oder Reglemente des Verbands dies vorsehen oder die Parteien eine besondere Schiedsvereinbarung ("specific arbitration agreement") abgeschlossen haben.
Das TAS befand zunächst, dass sich seine Zuständigkeit nicht auf die Statuten und anwendbaren Verbandsreglemente stützen lasse. Zwar sei der Beschwerdegegner den Regeln des Beschwerdeführers unterworfen und kraft Verweises an die Anti-Doping-Regeln und Verfahrensbestimmungen der IAAF gebunden. Diese sähen jedoch eine wichtige Unterscheidung zwischen nationalen ("National-Level") und internationalen Athleten ("International-Level Athletes") vor in Bezug auf Dopingkontrollen und die Beschwerdemöglichkeit an das TAS. Beim Beschwerdegegner handle es sich um einen nationalen Athleten ("National-Level Athlete") im Sinne der anwendbaren Anti-Doping-Regeln der IAAF. Als solcher sei er nach Artikel 60.12 der IAAF Competition Rules nicht zur Berufung an das TAS berechtigt, die gemäss Artikel 60.11 nur internationalen Athleten zur Verfügung stehe. Das TAS wies auch das Argument des Beschwerdegegners zurück, die vorgesehene Anfechtungsmöglichkeit an das South African Institute for Drug Free Sport genüge aufgrund von bestehenden Interessenkonflikten rechtsstaatlichen Anforderungen nicht, zumal darüber nach Ansicht des TAS die südafrikanischen Gerichte zu entscheiden hätten und die entsprechenden Vorbringen nicht geeignet seien, eine Zuständigkeit des TAS zu begründen.
Die Vorinstanz prüfte in der Folge, ob in dem vom IAAF Anti-Doping Administrator Dr. C._ verfassten Fax-Schreiben vom 10. April 2008 eine besondere Schiedsvereinbarung ("specific arbitration agreement") im Sinne von Artikel R47 des TAS-Code erblickt werden könne. Dabei hielt es fest, dass eine allfällige Schiedsvereinbarung den Voraussetzungen von <ref-law> zu genügen habe und erklärte im Übrigen - was von keiner Partei in Frage gestellt wird - für die Frage des Zustandekommens einer solchen Vereinbarung schweizerisches Recht für anwendbar (vgl. <ref-law>).
Das erwähnte Schreiben ist an den damaligen Rechtsvertreter des Beschwerdegegners gerichtet und bezweckte, diesen unter Eingeständnis eines Dopingvergehens sowie Anerkennung einer zweijährigen Sperre zu einem Vergleich zu bewegen. Es enthält unter anderem den folgenden Wortlaut:
"I would remind you that the decision that will ultimately be taken by the relevant disciplinary commission of [the national athletics federation] after 16th May will still be subject to an appeal to the Court of Arbitration for Sport in Lausanne, on your initiative if you disagree with it or on the initiative of IAAF, if the decision is not in accordance with the IAAF Rules. This will inevitably lead to a costly and lengthy arbitration procedure until the final award is rendered by CAS."
Der Beschwerdegegner schlug das Angebot von Dr. C._ aus, berief sich jedoch später hinsichtlich der Zuständigkeit des TAS auf die zitierte Äusserung. Das TAS hielt angesichts des Schreibens vom 10. April 2008 dafür, der Beschwerdegegner habe sich nach Treu und Glauben auf das Angebot der IAAF zum Abschluss einer Schiedsvereinbarung verlassen dürfen, und er habe durch Einreichung der Berufung beim TAS danach gehandelt. Der Beschwerdeführer habe Kenntnis vom erwähnten Schreiben gehabt und habe der von Dr. C._ im Namen der IAAF angebotenen Anfechtungsmöglichkeit zugestimmt.
Im Weiteren habe der Beschwerdegegner das Schreiben vom 10. April 2008 als Verweis auf das Verfahren nach Artikel 60.12 der IAAF Competition Rules verstehen dürfen, der eine Berufung an das TAS für nationale Athleten an sich ausschliesst, und er habe annehmen dürfen, dass die IAAF für ihn eine Ausnahme von dieser Bestimmung mache, indem sie eine direkte Anfechtung beim TAS nach Artikel 60.11 zulasse. Angesichts der langen Verfahrensdauer von mehr als zwei Jahren vor der Disziplinarkommission des Beschwerdeführers sowie dem anhaltenden Informationsaustausch ("ongoing communication") zwischen dem Beschwerdeführer und der IAAF habe der Beschwerdegegner das Verhalten dieser beiden Verbände nach Treu und Glauben dahingehend verstehen dürfen, dass diese kein Rechtsmittel auf nationaler Ebene, sondern eine direkte Anfechtung beim TAS wünschten.
Die Entscheidung der Disziplinarkommission des Beschwerdeführers vom 11. Dezember 2008 enthalte zudem weder einen Hinweis auf ein Rechtsmittelverfahren noch bestreite sie den Inhalt des Schreibens der IAAF. Dem Beschwerdeführer sowie dessen Disziplinarkommission sei die Existenz des Schreibens von Dr. C._ vom 10. April 2008 bewusst gewesen und die Disziplinarkommission hätte den Beschwerdegegner darauf aufmerksam machen müssen, dass nur ein innerstaatliches Rechtsmittel zur Verfügung stehe, wenn ihrer Ansicht nach kein direktes Rechtsmittel an das TAS offen stand. Der Beschwerdegegner habe dieses Schweigen nach Treu und Glauben als Zustimmung des Beschwerdeführers zum Schreiben von Dr. C._ verstehen dürfen.
Das TAS erachtete das Schreiben der IAAF vom 10. April 2008 an den damaligen Rechtsvertreter des Beschwerdegegners gestützt auf diese Überlegungen als besondere Schiedsvereinbarung ("specific arbitration agreement") und erklärte sich zur Beurteilung der Berufung des Beschwerdegegners für zuständig.
3.2 Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt, in rechtlicher Hinsicht frei. Demgegenüber überprüft es die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733).
3.3 Strittig ist im vorliegenden Verfahren zunächst, ob der Beschwerdegegner das Schreiben der IAAF vom 10. April 2008 nach Treu und Glauben (<ref-law>) als Angebot zum Abschluss einer Schiedsvereinbarung betrachten durfte.
Wie die Vorinstanz zutreffend festhält, hat eine allfällige Schiedsvereinbarung den Anforderungen von <ref-law> zu genügen. Während einerseits die Formerfordernisse nach Abs. 1 erfüllt sein müssen, richten sich die inhaltlichen Voraussetzungen nach Abs. 2 dieser Bestimmung. Das Schiedsgericht prüfte das Zustandekommen der fraglichen Schiedsvereinbarung - was von keiner Partei in Frage gestellt wird - in Anwendung von <ref-law> nach schweizerischem Recht.
Der notwendige Inhalt einer Schiedsvereinbarung wird durch das Gesetz nicht definiert. Es ergibt sich aus dem Zweck der Schiedsvereinbarung, dass der Wille der Parteien zum Ausdruck kommen muss, über bestimmte bestehende oder künftige Streitigkeiten ein Schiedsgericht, d.h. ein nicht staatliches Gericht, entscheiden zu lassen (<ref-ruling> E. 3.1 S. 70; <ref-ruling> E. 2.3 S. 679 mit Hinweisen).
Wie andere formbedürftige Rechtsgeschäfte ist auch eine Schiedsvereinbarung (<ref-law>) in einem ersten Schritt nach den allgemeinen Grundsätzen auszulegen (<ref-ruling> E. 3.2 S. 71 f. mit Hinweisen). Anschliessend ist in einem weiteren Schritt zu beurteilen, ob der nach den allgemeinen Auslegungsmethoden ermittelte Vertragsinhalt in der gesetzlich vorgeschriebenen Form hinreichend zum Ausdruck gebracht worden ist (vgl. <ref-ruling> E. 4 S. 366). Die ausführlichen Darlegungen der Vorinstanz zur Frage der massgebenden Form sowie ihre Hinweise auf die grosszügige Rechtsprechung des Bundesgerichts hinsichtlich der Formgültigkeit von Schiedsvereinbarungen im Bereich der internationalen Schiedsgerichtsbarkeit (vgl. <ref-ruling> E. 4.3.2.3 S. 244 f.) sind demnach nur von Bedeutung, wenn die Auslegung der zu beurteilenden Erklärungen überhaupt zur Annahme eines Vertragsschlusses führt. Von vornherein nicht relevant sind hingegen die Ausführungen im angefochtenen Entscheid zur bundesgerichtlichen Rechtsprechung hinsichtlich der Wirksamkeit von globalen Verweisungen auf in Verbandsstatuten enthaltene Schiedsklauseln (<ref-ruling> E. 4.3.2.3 S. 244 f.; Urteil 4A_358/2009 vom 6. November 2009 E. 3.2.4; je mit Hinweisen). Zum einen ist die Anwendbarkeit der Verbandsregeln über das Anfechtungsverfahren (Artikel 60.9 ff. IAAF Competition Rules) gar nicht strittig (diese sehen aber gemäss dem angefochtenen Entscheid im konkreten Fall keine Zuständigkeit des TAS vor), zum anderen lässt sich im zitierten Schreiben der IAAF vom 10. April 2008 ohnehin kein Verweis erkennen.
3.3.1 Das TAS hat im Zusammenhang mit der strittigen Schiedsvereinbarung wie erwähnt (vorn E. 2.5.2) keine tatsächliche Willensübereinstimmung der Parteien feststellen können. Es hat daher das Schreiben der IAAF vom 10. April 2008 an den damaligen Rechtsvertreter des Beschwerdegegners sowie das Verhalten des Beschwerdeführers zutreffend nach dem Vertrauensgrundsatz ausgelegt (vgl. <ref-ruling> E. 2.3.2 S. 274 f.; <ref-ruling> E. 3.2 S. 71 f.; je mit Hinweisen). Danach sind die Willenserklärungen der Parteien so auszulegen, wie sie nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen verstanden werden durften und mussten (<ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 2.3.2 S. 275; <ref-ruling> E. 3.2 S. 424 f., 686 E. 4.3.1 S. 689; je mit Hinweisen).
Die objektivierte Auslegung nach dem Vertrauensprinzip entscheidet auch darüber, ob überhaupt eine Willenserklärung vorliegt (Gauch/Schluep/Schmid, Schweizerisches Obligationenrecht, Allgemeiner Teil, Bd. I, 9. Aufl. 2008, Rz. 208; Alfred Koller, Schweizerisches Obligationenrecht, Allgemeiner Teil, 3. Aufl. 2009, § 3 Rz. 184; Ingeborg Schwenzer, Schweizerisches Obligationenrecht, Allgemeiner Teil, 5. Aufl. 2009, Rz. 27.43; Urteil 4A_437/2007 vom 5. Februar 2008 E. 2.4; vgl. <ref-ruling> E. 2b/bb S. 200; <ref-ruling> E. 2b S. 696). Es ist demnach zu beurteilen, ob ein bestimmtes Erklärungsverhalten vom Empfänger nach Treu und Glauben als Willensäusserung verstanden werden durfte, rechtsgeschäftlich tätig zu werden und sich ihm gegenüber rechtlich zu verpflichten. Von einem Antrag (<ref-law>) kann nur gesprochen werden, wenn die Erklärung einen hinreichenden Bindungswillen der erklärenden Partei erkennen lässt, mithin den Willen, im Falle der Annahme des Angebots gebunden zu sein (Schwenzer, a.a.O., Rz. 28.09).
3.3.1.1 Dr. C._ von der IAAF erinnerte den Rechtsvertreter des Beschwerdegegners im Schreiben vom 10. April 2008 daran, dass die Entscheidung der Disziplinarkommission, die voraussichtlich nach dem 16. Mai 2008 getroffen werde, noch beim TAS angefochten werden könne und eine solche Anfechtung unausweichlich zu einem kostspieligen und zeitraubenden Schiedsverfahren bis zu einem endgültigen Entscheid führen werde. Die Einleitung der von der Vorinstanz zitierten Passage des Schreibens ist nach ihrem Wortlaut ("I would remind you that") nicht als Erklärung zu verstehen, eine Verpflichtung gegenüber dem Adressaten einzugehen, sondern als Hinweis auf den nach Ansicht des Verfassers geltenden Rechtsmittelweg. Die Wortwahl ("will be subject to an appeal", "[t]his will lead to a costly and lengthy arbitration procedure", "final award is rendered by CAS") weist darauf hin, dass der Verfasser von einer bestimmten Vorstellung über das anwendbare Anfechtungsverfahren ausging, und den Adressaten auf dessen nachteilige Konsequenzen in Form von Kosten sowie langer Verfahrensdauer aufmerksam machen wollte. Nach der gewählten Formulierung wird vorausgesetzt, dass sich die beschriebene Anfechtungsmöglichkeit ohne Weiteres aus den anwendbaren Verfahrensvorschriften ergibt und diese dem Empfänger des Schreibens bekannt ist.
Nach ihrem Wortlaut ist die fragliche Passage demnach als Hinweis auf den vorgegebenen Verfahrensgang zu verstehen, der von den Parteien zu beachten ist. Ein Angebot zur Verpflichtung, die Anfechtung der Entscheidung der Disziplinarkommission in Abweichung der vorgegebenen Anfechtungsmöglichkeit einem Schiedsgericht zu unterbreiten, lässt sich daraus nicht ablesen. Überhaupt enthält der zitierte Auszug keine Anhaltspunkte, die den Empfänger zur Annahme berechtigen würden, der Verfasser wolle sich ihm gegenüber in verfahrensrechtlicher Hinsicht in irgendeiner Weise verpflichten.
3.3.1.2 Auch die Umstände lassen nach Treu und Glauben nicht darauf schliessen, Dr. C._ habe die IAAF (und damit schliesslich auch den Beschwerdeführer) mit dem Schreiben vom 10. April 2008 verpflichten wollen, den bestehenden Rechtsstreit in Abweichung der reglementarischen Anfechtungsmöglichkeiten einem internationalen Schiedsgericht zu unterbreiten.
Nach den verbindlichen Sachverhaltsfeststellungen der Vorinstanz (vgl. <ref-law>) richtete sich das Schreiben des Anti-Doping Administrators der IAAF, Dr. C._, an den damaligen Rechtsvertreter des Beschwerdegegners und bezweckte, das Verfahren vergleichsweise zu einem umgehenden Abschluss zu bringen. Hierzu bot Dr. C._ schriftlich an, die Angelegenheit mit einer zweijährigen Sperre zu erledigen, sofern der Beschwerdegegner das Dopingvergehen eingestehe. Gemäss dem angefochtenen Entscheid lehnte der Beschwerdegegner dieses Angebot ab. Es lassen sich den vorinstanzlichen Feststellungen keine Hinweise darauf entnehmen, dass die Parteien über weitere Punkte als die angebotene Vergleichslösung verhandelten. Das Schreiben vom 10. April 2008 war vielmehr auf das Angebot der beschleunigten Verfahrenserledigung gegen Anerkennung eines Dopingvergehens beschränkt. Ein doppeltes Angebot zur Beendigung des Verfahrens einerseits sowie - falls ein solcher Vergleich nicht zustande kommen sollte - zur schiedsgerichtlichen Beurteilung der Rechtsstreitigkeit durch das TAS andererseits ist nicht erkennbar.
Nach den Umständen des schriftlichen Vergleichsangebots vom 10. April 2008 ist der Hinweis auf die Zuständigkeit des TAS als Warnung hinsichtlich der damit verbundenen Verfahrensdauer und -kosten zu verstehen. Er diente als Argument dazu, den Beschwerdegegner gegen Zusicherung der Minimalstrafe zu einem Eingeständnis des Regelverstosses zu bewegen. Ein bedingter Antrag zur Änderung der reglementarischen Anfechtungsmöglichkeiten, falls das Vergleichsangebot ausgeschlagen wird, lässt sich darin nicht erkennen. Für dieses Verständnis spricht auch der Schlusssatz des Schreibens, wonach es nicht die Absicht der IAAF sei, in das laufende Disziplinarverfahren einzugreifen, sondern eine faire und zeitgerechte Vergleichslösung zu finden.
Das Schreiben erfolgte während des laufenden Disziplinarverfahrens, mithin rund acht Monate bevor ein Entscheid in der Sache erging. Der Umstand, dass der Disziplinarentscheid vom 11. Dezember 2008 keine Rechtsmittelbelehrung enthielt, war daher bereits aufgrund der zeitlichen Abläufe nicht geeignet, beim Empfänger des Schreibens vom 10. April 2008 eine nach Treu und Glauben zu schützende Erwartung hinsichtlich des darin erwähnten Anfechtungsverfahrens zu erwecken. Ohnehin ist nicht ersichtlich, inwiefern das Fehlen eines Hinweises hinsichtlich des Anfechtungsverfahrens eine Zuständigkeit des TAS begründen soll.
Der Beschwerdegegner bzw. sein Rechtsvertreter musste das Schreiben vom 10. April 2008 demnach nach Treu und Glauben wie folgt verstehen: Entweder er nimmt das Vergleichsangebot der IAAF an, womit die rückwirkend verhängte Sperre bereits am 24. April 2008 ablaufen würde und das Verfahren beendet wäre, oder er lehnt es ab und das Disziplinarverfahren nimmt seinen gewohnten Lauf. Eine Änderung des massgebenden Verfahrens im Falle der Ablehnung des Vergleichsvorschlags stand nicht zur Diskussion. Ein Angebot seitens der IAAF, dem Beschwerdegegner bei Zurückweisung des Vergleichsvorschlags eine nach den reglementarischen Vorgaben nicht vorhandene Anfechtungsmöglichkeit zu eröffnen, lässt sich aus dem zitierten Hinweis auf die Berufung an das TAS nicht ableiten.
Unzutreffend ist die Erwägung des angefochtenen Entscheids, das Schreiben enthalte einen impliziten Verweis auf Artikel 60.11 bzw. 60.12 der IAAF Competition Rules, die eine Anfechtung beim TAS nur für internationale Athleten vorsehen, und habe vom Beschwerdegegner so verstanden werden dürfen, dass für ihn - obwohl nationaler Athlet im Sinne dieser Bestimmungen - eine Ausnahme von den anwendbaren Verbandsregeln gemacht werde. Inwiefern sich dem Schreiben ein solcher Verweis auf die erwähnten Bestimmungen (deren Anwendbarkeit ohnehin unbestritten ist) ergeben soll, ist nicht nachvollziehbar. Noch viel weniger lässt sich - auch nicht mit dem Hinweis auf die ungewöhnlich lange Verfahrensdauer bzw. den anhaltenden Informationsaustausch zwischen dem Beschwerdeführer und der IAAF - eine konkrete Ausnahme von diesen Bestimmungen erkennen.
3.3.1.3 Aus dem Schreiben von Dr. C._ vom 10. April 2008 lässt sich weder nach seinem Wortlaut noch dem gesamten Zusammenhang der darin enthaltenen Äusserungen ein Angebot zum Abschluss einer Schiedsvereinbarung zugunsten des TAS ableiten. Die Auslegung des Schreibens nach dem Vertrauensgrundsatz führt vielmehr zum Ergebnis, dass sich die IAAF nur hinsichtlich des Vergleichsangebots rechtlich binden wollte; ein darüber hinausgehender Bindungswille für den Fall der Ablehnung der Vergleichslösung ist unter objektiven Gesichtspunkten nicht erkennbar.
3.3.2 Durfte der Beschwerdegegner das Schreiben vom 10. April 2008 nach Treu und Glauben nicht als Angebot der IAAF verstehen, den bestehenden Rechtsstreit dem TAS zu unterbreiten, so konnte er mit der Einreichung seiner Berufung beim TAS auch keinen Antrag annehmen und damit den Abschluss einer Schiedsvereinbarung bewirken. Damit fällt der auf dasselbe Schreiben gestützte Abschluss einer Schiedsvereinbarung mit dem Beschwerdeführer ebenfalls ausser Betracht. Die Frage nach der Formgültigkeit stellt sich folglich nicht.
Es braucht auch nicht auf die vom TAS geprüfte Frage eingegangen zu werden, ob die IAAF den Beschwerdeführer durch ihr Handeln wirksam hätte verpflichten können. Ohnehin sind die Ausführungen der Vorinstanz widersprüchlich, wenn sie einerseits praktisch durchwegs davon ausgeht, Dr. C._ habe im Namen der IAAF gehandelt, und sie andererseits eine Genehmigung eines Stellvertreterhandelns nach <ref-law> prüft.
Zwischen den Parteien ist entgegen dem angefochtenen Entscheid keine nach <ref-law> wirksame Schiedsvereinbarung zustande gekommen. Die Vorinstanz hat sich zur Beurteilung der vorliegenden Streitigkeit zu Unrecht gestützt auf das Schreiben vom 10. April 2008 für zuständig erklärt.
3.4 Der Beschwerdegegner bringt vor, das TAS hätte sich auf anderer Grundlage für zuständig erklären müssen.
Er stellt sich auf den Standpunkt, er sei entgegen dem angefochtenen Entscheid als internationaler Athlet ("International-Level Athlete") im Sinne der Anti-Doping-Regeln der IAAF zu qualifizieren, weshalb ihm der Weg an das TAS offen stehe.
3.4.1 Zwischen den Parteien ist unbestritten, dass der Beschwerdegegner nach Artikel 60.11 der IAAF Competition Rules zur Berufung an das TAS berechtigt wäre, falls er nach dieser Bestimmung als internationaler Athlet ("International-Level Athlete") zu gelten hätte.
Das IAAF Handbuch enthält hierzu die folgende Definition:
"International-Level Athlete
For the purposes of the Anti-Doping Rules (chapter 3) and Disputes (Chapter 4) an athlete, who is in the Registered Testing Pool for out-of-competition testing or who is competing in an International Competition under Rule 35.7".
Nach den Feststellungen des angefochtenen Entscheids, die von keiner Partei in Frage gestellt werden, war der Beschwerdegegner nicht im "Registered Testing Pool" verzeichnet. Streitig ist im vorliegenden Beschwerdeverfahren nurmehr, ob sich der vom Beschwerdegegner behauptete Status als internationaler Athlet ("International-Level Athlete") auf die Teilnahme an einem internationalen Wettkampf ("International Competition") stützen lässt.
3.4.2 Der angefochtene Schiedsentscheid hält fest, dass der Seoul Marathon nicht auf der IAAF-Liste der internationalen Veranstaltungen des Jahres 2006 verzeichnet war, jedoch in den folgenden Jahren heraufgestuft wurde und nunmehr auf der Liste der internationalen Wettkämpfe ("International Competition") figuriert.
Die Vorinstanz hat zutreffend erwogen, dass der Qualifikation einer Veranstaltung als internationaler Wettkampf ("International Competition") und damit zusammenhängend dem Status eines Sportlers als internationaler Athlet ("International-Level Athlete") nicht bloss verfahrensrechtliche Bedeutung zukommt. Vielmehr ist die Unterscheidung zwischen nationalen und internationalen Athleten massgebend für deren jeweilige Rechte und Pflichten im Rahmen der Anti-Doping-Regeln der IAAF. Entgegen der Ansicht des Beschwerdegegners ist die entsprechende Einordnung nicht einer verfahrensrechtlichen Vorschrift gleichzusetzen, die auch auf Sachverhalte anzuwenden ist, die sich vor ihrem Inkrafttreten ereignet haben.
Das Argument des Beschwerdegegners, im Zeitpunkt der Einleitung des Schiedsverfahrens Anfang 2009 sei der Seoul Marathon von der IAAF als internationaler Wettkampf klassifiziert gewesen, womit eine Anfechtung beim TAS offen stehe, verfängt nicht. Die vom TAS beurteilte Dopingprobe wurde anlässlich des Seoul Marathons 2006 entnommen, der von der IAAF nicht als internationaler Wettkampf anerkannt war. Der vorgesehene Rechtsweg, der gemäss Artikel 60.11 der IAAF Competition Rules an die Qualifikation als internationaler Wettkampf anknüpft, führt daher auch dann nicht an das TAS, wenn ein am selben Ort ausgetragener Wettkampf in späteren Jahren anders klassifiziert wird. Der Umstand, dass der Seoul Marathon 2008 (und gemäss dem angefochtenen Entscheid eventuell bereits derjenige des Jahres 2007) von der IAAF als internationaler Wettkampf anerkannt wurde, ändert nichts daran, dass der im Jahr 2006 durchgeführten Veranstaltung dieser Status nicht zukam. Die verfahrensrechtliche Vorschrift, nach der nur ein internationaler Athlet zur Anfechtung beim TAS berechtigt ist, blieb zudem unverändert. Es trifft daher entgegen der Ansicht des Beschwerdegegners nicht zu, dass seit der beurteilten Dopingprobe der anwendbare Rechtsmittelweg geändert worden wäre, der rückwirkend angewendet werden könnte.
Von komplexen Zuständigkeitsfragen aufgrund der Anwendbarkeit verschiedener staatlicher sowie vereinsrechtlicher Bestimmungen, wie sie dem in der Beschwerdeantwort erwähnten Entscheid (4P.149/2003 vom 31. Oktober 2003 E. 2.2.2) zugrunde lagen, kann vorliegend zudem nicht gesprochen werden. Ausserdem stand im besagten Entscheid die Ausschöpfung des Instanzenzugs vor Anrufung des TAS und nicht dessen Zuständigkeit an und für sich zur Diskussion. Entgegen der Ansicht des Beschwerdegegners lässt sich daraus nichts zu seinen Gunsten ableiten.
Eine Zuständigkeit des TAS lässt sich auch nicht mit dem Vorbringen begründen, die IAAF selbst habe den Beschwerdeführer über den positiv ausgefallenen Dopingtest informiert, womit es sich um einen "IAAF Test" im Sinne von Artikel 36.5 der IAAF Competition Rules handle, der nur bei internationalen Wettkämpfen nach Artikel 35.7 durchgeführt werde. Im entsprechenden Schreiben an den Beschwerdeführer vom 13. April 2006 stellte die IAAF gemäss dem angefochtenen Entscheid vielmehr klar, dass die Beurteilung der Testresultate - wie bei nationalen Wettkämpfen vorgeschrieben - dem Beschwerdeführer obliege. Der Beschwerdegegner stellt etwa auch nicht in Frage, dass die provisorische Sperre vom Beschwerdeführer als Nationalverband ausgesprochen wurde, wie dies in Artikel 38.2 für nationale Athleten vorgesehen ist. Unbehelflich ist zudem der Hinweis auf den Umstand, dass im Jahr 2006 Marathonveranstaltungen von der IAAF aus Versehen generell nicht als internationale Wettkämpfe aufgeführt worden waren und dies später korrigiert wurde. Aus welchen Gründen der Seoul Marathon 2006 von der IAAF nicht als internationaler Wettkampf anerkannt war, ist nicht entscheidend. Aus den Sachverhaltsfeststellungen des angefochtenen Entscheids ergibt sich jedenfalls nicht, dass der Seoul Marathon 2006 - auch wenn nicht als solcher aufgelistet - von der IAAF hinsichtlich der durchgeführten Dopingtests tatsächlich als internationaler Wettkampf nach Artikel 35.7 behandelt worden wäre.
3.4.3 Der Beschwerdegegner beruft sich im Hinblick auf die Zuständigkeit des TAS schliesslich vergeblich auf den Grundsatz der "lex mitior" nach Artikel 25.2 des World Anti-Doping Code der WADA.
Der Grundsatz besagt, dass - als Ausnahme vom Prinzip des Rückwirkungsverbots - das neue Recht auf ein vor dessen Inkrafttreten verübtes Dopingvergehen anzuwenden ist, wenn es eine mildere Strafe vorsieht als das alte Recht. Mit dem Hinweis darauf, es handle sich beim Schiedsverfahren vor dem TAS - im Gegensatz zum nationalen Verfahren - um ein unabhängiges, rasches und kostenfreies Schiedsverfahren, zeigt der Beschwerdegegner keine entsprechende Konstellation auf. Wie der Beschwerdeführer zutreffend vorbringt, findet der Grundsatz der "lex mitior" auf Strafen für Dopingfälle Anwendung, nicht jedoch auf eine Änderung anderer materiellrechtlicher Bestimmungen, die sich indirekt auf das anwendbare Beschwerdeverfahren auswirkt.
Es ist nicht ersichtlich, inwiefern sich aus dem genannten Grundsatz ein Anspruch auf Anfechtung des Entscheids beim TAS anstelle einer nationalen Instanz ergeben soll.
3.4.4 Der Vorinstanz ist keine Rechtsverletzung vorzuwerfen, wenn sie dem Beschwerdegegner den Status eines internationalen Athleten ("International-Level Athlete") abgesprochen und daher eine Zuständigkeit nach Artikel 60.11 der IAAF Competition Rules verneint hat.
4. Das TAS hat sich zu Unrecht gestützt auf das Schreiben vom 10. April 2008 für zuständig erklärt. Seine Zuständigkeit lässt sich auch nicht auf die anwendbaren verbandsrechtlichen Regelungen stützen. Der Entscheid der Vorinstanz vom 24. Juli 2009 ist demnach in Gutheissung der Beschwerde aufzuheben und die Vorinstanz für unzuständig zu erklären.
Dem Ausgang des Verfahrens entsprechend wird der Beschwerdegegner kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid der Vorinstanz vom 24. Juli 2009 wird aufgehoben.
2. Es wird festgestellt, dass die Vorinstanz zur Beurteilung der Berufung des Beschwerdegegners nicht zuständig ist.
3. Die Gerichtskosten von Fr. 5'000.-- werden dem Beschwerdegegner auferlegt.
4. Der Beschwerdegegner hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 6'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 3. Mai 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann