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.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht (Art. 105 Abs. 1 und 2 BGG).
2. Die Vorinstanz legt zutreffend dar, dass sich die Anspruchsberechtigung des Beschwerdeführers nach schweizerischem Recht beurteilt (Art. 4 Abkommen zwischen der Schweizerischen Eidgenossenschaft und der Republik Mazedonien über Soziale Sicherheit; SR 0.831.109.520.1) und intertemporalrechtlich die bis bis 31. Dezember 2007 gültig gewesenen Bestimmungen zur Anwendung gelangen. Korrekt sind auch die Ausführungen zu den Voraussetzungen, unter welchen die revisionsweise Aufhebung einer Invalidenrente zulässig ist (<ref-law>; <ref-ruling> E. 6.1 S. 546; <ref-ruling> E. 3.5 S. 349 ff.).
3. Streitig und zu prüfen ist, ob die Vorinstanz in bundesrechtskonformer Weise die von der Beschwerdegegnerin revisionsweise verfügte Rentenaufhebung geschützt hat.
4. 4.1 Das Bundesverwaltungsgericht erwog, der medizinische Rapport der Kommission für Einschätzung der Arbeitsfähigkeit der mazedonischen Alters- und Invalidenversicherung sei in Kenntnis der Anamnese und der relevanten Arztberichte erstellt worden. Die Aussagen seien nachvollziehbar und in sich widerspruchsfrei. Die Anforderungen an ein Beweismittel mit erhöhtem Beweiswert seien erfüllt, so dass die hierauf gestützte Einstellung der IV-Rente zu Recht erfolgt sei.
4.2 Der Beschwerdeführer rügt, der Beurteilung durch die mazedonischen Ärzte vom 22. Januar 2007 fehlten wesentliche Elemente eines beweistauglichen Gutachtens. Weder sei er über die Person der Gutachter vorgängig informiert worden noch hätten die Ärzte Kenntnis der Vorakten gehabt; es sei lediglich ein oberflächlicher, nicht auf seriösen Unterlagen gründender Bericht verfasst worden. So fehle in der Diagnoseliste die Arthritis urica, obwohl diese anlässlich der Untersuchungen in der mazedonischen Abklärungsstelle bestätigt worden sei. Auch habe keine körperliche Untersuchung stattgefunden; er habe mit zuvor angefertigten Röntgenbildern erscheinen müssen und die Begutachtung habe sich auf ein kurzes Gespräch mit einem mazedonisch (nicht albanisch) sprechenden Arzt beschränkt. Er leide nach wie vor mehrmals im Monat unter Gichtanfällen und sein dann jeweils kaum in der Lage, das Bett zu verlassen.
5.1 5.1.1 Der Bericht der mazedonischen Abklärungsstelle vom 22. Januar 2007 umfasst sowohl eine Anamnese als auch eine Befundaufnahme (Untersuchung von Kopf und Hals, Thorax, Lunge und Herz, Abdomen, Wirbelsäule Extremitäten, Psycho- und Neurostatus), ferner Laboruntersuchungen vom 13. September 2006 sowie Untersuchungen durch einen Orthopäden (vom 18. September 2006) und durch einen Internisten (vom 12. Januar 2007). Aktenkundig sind des Weiteren Röntgenbilder vom 26. November und 20. Dezember 2006. Die Ärzte hielten fest, der Versicherte habe eine Verbesserung seines Gesundheitszustandes nach 1997 geschildert. Er lebe seit dem Jahre 2005 in Mazedonien, wo er sich periodisch hausärztlichen Kontrollen unterziehe; neue Spitalaufenthalte seien nicht zu verzeichnen. Als Diagnosen (mit Auswirkungen auf die Arbeitsfähigkeit) werden eine Gonarthrose (Arthrose im Kniegelenk; M17) bzw. eine beidseitige beginnende Gonarthrose angeführt und in der angestammten Tätigkeit eine vollumfängliche Arbeitsfähigkeit attestiert.
5.1.2 Dr. med. S._ diagnostizierte am 21. September 2007 nebst einer Spondylose auch eine Discopathie (L5-S1), eine Coxarthrose sowie eine Arthritis urica. Sinngemäss führte er aus, der Gesundheitszustand des Versicherten sei in den letzten Monaten nicht besser geworden, sondern die Erkrankung schreite immer mehr fort. Der Versicherte solle folgende Medikamente nehmen: 2 x 1 Tablette Alopurinol 100 mg sowie 2 x 1⁄4 Tablette Decortim H 20 mg. Zudem solle er Borwasser 3 % (sol Ac. borici 3 %) anwenden und schliesslich habe er Diät zu halten und zu ruhen.
5.2 Selbst wenn gewisse Zweifel an den gestützt auf den mazedonischen Abklärungsbericht vom 22. Januar 2007 ergangenen vorinstanzlichen Feststellungen bestehen bleiben, wonach sich der Gesundheitszustand des Beschwerdeführers in revisionsrechtlich relevantem Ausmass verbessert hat, können diese weder als qualifiziert unrichtig noch die Beweiswürdigung im angefochtenen Entscheid als willkürlich im Sinne von <ref-law> bezeichnet werden. Willkür liegt nur vor, wenn die Sachverhaltsfeststellung zur tatsächlichen Situation in klarem Widerspruch steht oder auf einem offenkundigen Fehler beruht. Dass eine andere Lösung oder Würdigung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, genügt für die Annahme von Willkür nicht (<ref-ruling> E. 5.4 S. 148). Ein klarer Widerspruch oder ein offensichtlicher Fehler kann der Vorinstanz nicht unterstellt werden. Insbesondere bestätigte der behandelnde Dr. med. S._, dessen Bericht vom 21. September 2007 mit besonderer Sorgfalt zu würdigen ist (<ref-ruling> E. 3a/cc S. 353; Urteil 9C_204/2009 vom 6. Juli 2009 E. 4.4.1, nicht publiziert in <ref-ruling>, aber in: SVR 2009 IV Nr. 53 S. 164), die vom Versicherten dramatisch geschilderten Gichtschübe nicht. Im Gegenteil führte er die Arthritis urica erst an letzter Stelle seiner Diagnoseliste an und erklärte in der Kurzbegründung lediglich, der Beschwerdeführer klage über Schmerzen "auf dem oberen Teil von LS", zudem sei die Beweglichkeit von "LS Rückgrat" und Hüften beschränkt. Die von Dr. med. S._ installierte Medikation steht einer Verbesserung der Gichtproblematik ebenfalls nicht entgegen. So entspricht die Dosierung des zur Gichttherapie eingesetzten Medikamentes "Allopurinol 100 mg" von 200 mg täglich der üblichen Therapie für einen leichten Fall (Quelle: open drug database; http.//ch.oddb.org) und der Entzündungshemmer "Decortin 20 mg", welchen der Beschwerdeführer in der Dosis von 10 mg täglich einnehmen soll, liegt ebenfalls auf der Dosierungsstufe sehr niedrig bzw. niedrig (Quelle: open drug database). Nebst dem Borwasser (mildes Antiseptikum) und der bereits im Jahre 1996 einzuhaltenden Diät ordnete Dr. med. S._ keine weitere Therapie an und hinsichtlich der Arbeitsunfähigkeit lässt sich seinem Bericht nichts entnehmen.
5.3 Die revisionsweise Aufhebung (oder Herabsetzung) einer Rente kann erst erfolgen, wenn die versicherte Person im Rahmen des Zumutbaren bestmöglich eingegliedert ist. Die Eingliederungsfrage ist auch im Revisionsverfahren prioritär und von Amtes wegen zu prüfen, woran grundsätzlich nichts ändert, wenn sich die versicherte Person im Ausland befindet (hingegen gelten für die Kostenübernahme von Eingliederungsmassnahmen im Ausland besondere Anforderungen; <ref-law>). Die Verwaltung hat somit vorgängig abzuklären, ob und in welchem Mass der Versicherte infolge seines gebesserten Gesundheitszustandes auf dem ihm nach seinen Fähigkeiten offen stehenden ausgeglichenen Arbeitsmarkt zumutbarerweise erwerbstätig sein könnte. Gegen eine Revision ist - unter Beachtung von Art. 88a und 88bis IVV - nichts einzuwenden, sofern die versicherten Person in der Lage ist, die wiedergewonnene Arbeitsfähigkeit auf dem Weg der Selbsteingliederung erwerblich zu verwerten (Ulrich Meyer, Bundesgesetz über die Invalidenversicherung [IVG], 2010, S. 383 mit Hinweisen).
5.4 Die Annahme von Beschwerdegegnerin und kantonalem Gericht, der Beschwerdeführer könne ohne weiteres wieder in der angestammten Tätigkeit (Hotellerie) ein rentenausschliessendes Erwerbseinkommen erzielen, wird zwar durch die Beurteilung der mazedonischen Abklärungsstelle gestützt. Indes fehlt eine diesbezügliche Begründung im Bericht vom 22. Januar 2007 gänzlich, weshalb erhebliche Zweifel bestehen, ob die dortigen Mediziner die Arbeitsfähigkeit des Versicherten mit der gebotenen Sorgfalt untersucht haben. Auf deren unbegründet gebliebene Schlussfolgerungen kann nicht abgestellt werden (<ref-ruling> E. 3a S. 352), umso weniger, als auch Dr. med. L._ vom medizinischen Dienst der IVSTA am 1. Mai 2008 zum Schluss gelangte, aufgrund der Akten bestehe zwar in sitzenden/abwechselnden, eher körperlich leichten Arbeiten eine uneingeschränkte Arbeitsfähigkeit, indes sei der Versicherte in rein stehenden Tätigkeiten (am gleichen Ort) "wohl eher nicht mehr einsetzbar wegen der Minderbelastung der Gelenke (Knie)". Seiner Ansicht nach sei der Beschwerdeführer als Kellner höchstens halbtägig einsetzbar. Zumutbar wären beispielsweise Überwachungstätigkeiten in einem Parkhaus oder Museum, die Arbeit als Magaziner, kleine Auslieferungen mit einem Fahrzeug, Reparaturen von Kleinapparaten, Billettverkäufer, interne Kurier- oder Botendienste, Tätigkeit als Rezeptionist oder am Empfang oder in der Datenerfassung/Scannen. Ob der 1948 geborene Beschwerdeführer, welcher in dem für die richterliche Beurteilung massgebenden Zeitpunkt des Erlasses der angefochtenen Verfügung (31. August 2008) rund 60 Jahre alt war und der zwar in Mazedonien eine zweijährige "Metallschule" absolviert, indes seit seiner Einreise in die Schweiz im Jahre 1977 bis zur Aufgabe der Erwerbstätigkeit ca. 1995 als Kellner gearbeitet hatte, seine Arbeitsfähigkeit auf dem ausgeglichenen Arbeitsmarkt verwerten könnte, ist gestützt auf die vorhandenen Akten nicht abschliessend beurteilbar. Die Sache wird daher an die IVSTA zurückgewiesen, damit sie ergänzende Abklärungen hinsichtlich der Verwertbarkeit der Arbeitsfähigkeit in die Wege leite.
5.5 Abschliessend ist festzuhalten, dass der mit der revisionsweise verfügten Aufhebung einer Rente oder Hilflosenentschädigung verbundene Entzug der aufschiebenden Wirkung der Beschwerde bei Rückweisung der Sache an die Verwaltung auch für den Zeitraum dieses Abklärungsverfahrens bis zum Erlass der neuen Verwaltungsverfügung andauert (<ref-ruling> E. 4.3 S. 375 f.).
6. Die Kosten des Verfahrens sind ausgangsgemäss von der unterliegenden IV-Stelle zu tragen (<ref-law>), welche dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung zu bezahlen hat (<ref-law>). Mit Blick darauf, dass Rechtsanwalt Gerold Meier den Versicherten schon vor Bundesverwaltungsgericht vertreten hat und ihm die Akten somit bekannt waren, was bei der Honorarforderung zu berücksichtigen ist (vgl. Urteil U 154/04 vom 16. Januar 2006 E. 6.3), besteht kein Grund, eine höhere Entschädigung als den gerichtsüblichen Pauschalansatz von Fr. 2'800.- zuzusprechen. Das Gesuch um unentgeltliche Prozessführung und Verbeiständung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Bundesverwaltungsgerichts vom 16. September 2009 und die Verfügung der IV-Stelle für Versicherte im Ausland vom 31. August 2008 werden aufgehoben. Die Sache wird an die IV-Stelle für Versicherte im Ausland zurückgewiesen, damit sie im Sinne der Erwägungen weitere Abklärungen in die Wege leite und danach über den Anspruch des Beschwerdeführers auf eine Rente der Invalidenversicherung ab 1. November 2007 neu entscheide.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen und diesen Betrag Rechtsanwalt Gerold Meier zu überweisen.
4. Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Bundesverwaltungsgericht zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Bundesverwaltungsgericht und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 22. Juni 2010
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle