Sachverhalt: A. A.a I._, geboren 1948, meldete sich am 25. Juni 1997 bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle des Kantons Schaffhausen führte erwerbliche und medizinische Abklärungen durch. Mit Verfügung vom 14. Juli 1999 sprach sie I._ ab 1. Juni 1997 eine ganze Invalidenrente bei einem Invaliditätsgrad von 88 % zu. Diesen Anspruch bestätigte sie mit Verfügung vom 9. Oktober 2002. Nachdem I._ nach Mazedonien zurückgekehrt war, erklärte das Ausländeramt des Kantons Schaffhausen mit Verfügung vom 24. September 2004 die Niederlassungsbewilligung als erloschen. A.b Im Rahmen eines Revisionsverfahrens veranlasste die zuständig gewordene IV-Stelle für Versicherte im Ausland, Genf (im Folgenden: IVSTA), medizinische Abklärungen bei der mazedonischen Abklärungsstelle (Fonds de l'assurance vieillesse et invalidité de la Macedonie, Skopje; Bericht vom 22. Januar 2007). Nach Eingang einer Stellungnahme des RAD (Dr. med. C._) vom 6. Juni 2007 und durchgeführtem Vorbescheidverfahren verfügte die Zentrale Ausgleichsstelle (ZAS) der IVSTA am 31. August 2007, ab dem 1. November 2007 bestehe kein Anspruch mehr auf eine Invalidenrente. B. Die hiegegen erhobene Beschwerde des I._, mit welcher er einen Bericht des Dr. med. S._, Facharzt für Orthopädie, Mazedonien, vom 21. September 2007, zu den Akten reichen liess, wies das Bundesverwaltungsgericht mit Entscheid vom 16. September 2009 ab, nachdem die IVSTA eine Einschätzung ihres Medizinischen Dienstes (Dr. med. L._) vom 1. Mai 2008 ins Recht gelegt hatte. C. I._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, in Aufhebung des angefochtenen Entscheides sei ihm die "einstmals zugesprochene IV-Rente weiterhin auszurichten". Gleichzeitig ersucht er um Gewährung der unentgeltlichen Prozessführung und Verbeiständung. Die IVSTA schliesst auf Abweisung der Beschwerde. Das Bundesverwaltungsgericht und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung. 