Sachverhalt:
A. A.a Der 1966 geborene S._ war bis 1998 in der Schweiz erwerbstätig. Am 25. Februar 1999 meldete er sich bei der IV-Stelle des Kantons Zürich zum Leistungsbezug an. Mit Verfügung vom 10. Juni 2000 sprach ihm die IV-Stelle bei einem Invaliditätsgrad von 100 % eine ganze Rente der Invalidenversicherung zu.
A.b Die nach dem Wegzug von S._ ins Ausland zuständige IV-Stelle für Versicherte im Ausland (IVSTA) leitete am 14. November 2006 ein Revisionsverfahren ein. Sie klärte den Sachverhalt ab und holte unter anderem bei Dr. med. T._, Kosovo, am 22. März 2007 ein psychiatrisches Gutachten ein, in dem dieser eine Arbeitsunfähigkeit von noch 20 % in angepassten Verweistätigkeiten bescheinigte. Mit Verfügung vom 16. Oktober 2007 stellte die IVSTA die Ausrichtung der Rente per 1. Dezember 2007 ein. Das Bundesverwaltungsgericht hiess mit Entscheid vom 6. Juni 2008 die dagegen erhobene Beschwerde gut und wies die Sache an die IVSTA zur weiteren Abklärung zurück. Das Medizinische Abklärungszentrum X._ erstattete am 10. April 2009 ein interdisziplinäres medizinisches Gutachten und kam zum Ergebnis, S._ sei in der zuletzt ausgeübten wie auch in allen Verweistätigkeiten seit Anfang 2007 zu 100 % arbeitsfähig. Mit Verfügung vom 15. Oktober 2009 verneinte die IVSTA ab 1. Dezember 2007 den Anspruch auf eine Invalidenrente erneut.
B. Die hiegegen eingereichte Beschwerde hiess das Bundesverwaltungsgericht mit Entscheid vom 28. Juni 2011 teilweise gut, indem es die Invalidenrente erst per 1. Dezember 2009 aufhob.
C. C.a Mit Beschwerde beantragt die IVSTA die Aufhebung der Dispositiv-Ziffer 1 des vorinstanzlichen Entscheides und die vollumfängliche Bestätigung ihrer Verfügung vom 16. Oktober 2009. Der Beschwerde sei zudem aufschiebende Wirkung zuzuerkennen.
C.b S._ lässt ebenfalls Beschwerde führen. Er beantragt über den 1. Dezember 2009 hinaus die Ausrichtung einer unbefristeten ganzen Invalidenrente. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
C.c Die IVSTA wie auch S._ beantragen die Abweisung der Beschwerde der Gegenpartei. Gegen die Erteilung der aufschiebenden Wirkung hatte S._ nichts einzuwenden.
C.d Mit Verfügung vom 18. Oktober 2011 wurde der Beschwerde der IVSTA die aufschiebende Wirkung zuerkannt.
C.e In der Vernehmlassung vom 8. November 2011 beantragt das Bundesamt für Sozialversicherungen die Gutheissung der Beschwerde der IVSTA und die Aufhebung der Rente per 1. Dezember 2007.

Erwägungen:
1. Da den beiden Beschwerden derselbe Sachverhalt zugrunde liegt, sich die gleichen Rechtsfragen stellen und die Rechtsmittel den nämlichen vorinstanzlichen Entscheid betreffen, rechtfertigt es sich, die beiden Verfahren zu vereinigen und in einem einzigen Urteil zu erledigen (<ref-ruling> E. 1 S. 126 mit Hinweisen).
2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann eine - für den Ausgang des Verfahrens entscheidende (vgl. <ref-law>) - Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder wenn sie auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>).
3. 3.1 Die IVSTA und das Bundesamt für Sozialversicherungen rügen, die Vorinstanz gehe in bundesrechtswidriger Anwendung von <ref-law> davon aus, diese Bestimmung lasse eine Rentenaufhebung erst ab dem ersten Tag des zweiten der Zustellung der angefochtenen Verfügung vom 15. Oktober 2009 folgenden Monats zu, obwohl das Gutachten des Medizinischen Abklärungszentrums X._ eine relevante Besserung im Frühjahr 2007 bescheinigt und damit die rentenaufhebende Revisionsverfügung vom 16. Oktober 2007 bestätigt habe.
3.2 Mit Verfügung vom 16. Oktober 2007 stellte die IVSTA die Ausrichtung der Rente per 1. Dezember 2007 ein. Nachdem die Vorinstanz diese Verfügung aufgehoben hatte und das daraufhin eingeholte interdisziplinäre Gutachten ebenfalls zum Schluss einer erheblichen Besserung des Gesundheitszustandes im Frühjahr 2007 gekommen war, bestätigte die IVSTA mit Verfügung vom 15. Oktober 2009 erneut die Renteneinstellung per 1. Dezember 2007. Die Vorinstanz führte aus, das Gutachten des Medizinischen Abklärungszentrums X._, das im April 2009 erstellt worden sei, stelle eine neue Grundlage für die Beurteilung des Rentenanspruchs dar, weshalb die Rente in Anwendung von <ref-law> per 1. Dezember 2009 aufzuheben sei.
Diese Auffassung erweist sich als bundesrechtswidrig. Massgeblich für die Rentenaufhebung ist, ab welchem Zeitpunkt die Ärzte eine zumutbare Arbeitsfähigkeit attestieren; bestätigen die erneuten medizinischen Untersuchungen die medizinischen Feststellungen im Rahmen der ersten Abklärungen auch in zeitlicher Hinsicht (Beginn der zumutbaren Arbeitsfähigkeit), war der ursprüngliche Entscheid korrekt. Denn auch im Rahmen der Rückweisung bleibt streitig, ob die IV-Stelle anlässlich der ersten Verwaltungsverfügung zu Recht den Leistungsanspruch reduziert resp. aufgehoben hat. Eine Rückweisung bedeutet nicht zwingend, dass die Feststellungen in der ersten Verwaltungsverfügung falsch waren, sondern bloss, dass diese beim derzeitigen Abklärungsstand nicht bestätigt werden konnten. Somit ist nur für den Fall, dass eine relevante zumutbare Arbeitsfähigkeit erst nach Erlass der ersten Verwaltungsverfügung eingetreten ist und zu einer Rentenherabsetzung oder -aufhebung führt, der entsprechende Verwaltungs- oder Gerichtsentscheid massgebend für den Beginn der Frist von <ref-law> (Herabsetzung oder Aufhebung der Leistung frühestens vom ersten Tag des zweiten der Zustellung der Verfügung folgenden Monats). Oder kurz gesagt: Eine Rentenaufhebung oder -herabsetzung kann nicht rückwirkend verfügt, wohl aber rückwirkend bestätigt werden (<ref-ruling>; <ref-ruling>; SVR 2011 IV Nr. 33 S. 96, 8C_451/2010 E. 4.2.2 und E. 4.2.3; Urteile 8C_528/2010 vom 20. Dezember 2010, 8C_543/2010 vom 20. Dezember 2010 und 9C_301/2010 vom 21. Januar 2011).
Soweit vorliegend eine Verbesserung des Gesundheitszustands zu berücksichtigen ist und damit die Ausrichtung der Invalidenrente eingestellt wird, hat diese somit auf den 1. Dezember 2007 zu erfolgen.
4. Streitig und zu prüfen ist sodann, ob die Vorinstanz den seit August 1998 bestehenden Anspruch des Versicherten auf eine ganze Rente der Invalidenversicherung im Rahmen der vorliegenden Revision verneinen durfte, weil sich sein Gesundheitszustand leistungswirksam verbessert hat (<ref-law>).
4.1 Ändert sich der Invaliditätsgrad einer Rentenbezügerin oder eines Rentenbezügers erheblich, so wird die Rente von Amtes wegen oder auf Gesuch hin für die Zukunft entsprechend erhöht, herabgesetzt oder aufgehoben (<ref-law>; vgl. auch Art. 87 Abs. 2 und 3, Art. 88a und Art. 88bis IVV). Anlass zur Revision von Invalidenrenten gibt jede Änderung in den tatsächlichen Verhältnissen, die geeignet ist, den Invaliditätsgrad und damit den Rentenanspruch zu beeinflussen. Die Invalidenrente ist daher nicht nur bei einer wesentlichen Veränderung des Gesundheitszustandes, sondern auch dann etwa revidierbar, wenn sich die erwerblichen Auswirkungen des an sich gleich gebliebenen Gesundheitszustandes erheblich verändert haben oder eine andere Art der Bemessung der Invalidität zur Anwendung gelangt (<ref-ruling> E. 3.5 S. 349). Als Vergleichsbasis für die Beurteilung der Frage, ob bis zum Abschluss des aktuellen Verwaltungsverfahrens eine anspruchserhebliche Änderung des Invaliditätsgrades eingetreten ist, dient die letzte rechtskräftige Verfügung, welche auf einer materiellen Prüfung des Rentenanspruchs mit rechtskonformer Sachverhaltsabklärung, Beweiswürdigung und Durchführung eines Einkommensvergleichs beruht (<ref-ruling>).
4.2 Die abweichende medizinische oder rechtliche Einschätzung von im Wesentlichen unveränderten tatsächlichen Verhältnissen führt nicht zu einer materiellen Revision. Bloss auf einer anderen Wertung beruhende, revisionsrechtlich unerhebliche Differenzen sind daher von revisionsbegründenden tatsächlichen Veränderungen abzugrenzen. Eine Veränderung von versicherungsmedizinischen Beurteilungsparametern kann zu einer abweichenden ärztlichen Schlussfolgerung hinsichtlich eines tatsächlich gleich gebliebenen Zustandes führen. Eine neue medizinische Beurteilung etwa, die mit der Entwicklung der Rechtspraxis zur Invalidität bei psychosomatischen Leiden (<ref-ruling>; <ref-ruling>; vgl. auch <ref-ruling> und 132 V 65) begründet wird, kann weder unter dem Gesichtspunkt von <ref-law> noch unter einem anderen Anpassungstitel eine neue Beurteilung des Anspruchs veranlassen (<ref-ruling> und 215). Eine zwischenzeitlich veränderte Rechtspraxis darf erst im Rahmen einer festgestellten erheblichen Tatsachenänderung berücksichtigt werden. Sie könnte auch nicht als Grundlage für eine Wiedererwägung herangezogen werden, weil deren Voraussetzungen vor dem Hintergrund der Rechtspraxis im Zeitpunkt der rechtskräftigen Leistungszusprechung beurteilt werden (Urteil 9C_418/2010 vom 29. August 2011 E. 4.1 mit Hinweisen).
5. Bezogen auf den vorliegenden Fall ist zu prüfen, ob die vorinstanzliche Auffassung, wonach im massgebenden Beurteilungszeitraum eine Verbesserung der psychischen Leiden eingetreten sei, vor Bundesrecht standhält.
5.1 Die auf der Würdigung der ärztlichen Befunde beruhende vorinstanzliche Feststellung, dass und inwiefern seit der ursprünglichen Rentenzusprechung eine Veränderung in den gesundheitlichen Verhältnissen (vgl. Urteil I 692/06 vom 19. Dezember 2006 E. 3.1) eingetreten ist, bindet das Bundesgericht (Art. 97 Abs. 1, Art. 105 Abs. 1 und 2 BGG). Insoweit hat die Frage, ob im Einzelfall eine substanzielle Veränderung der Faktenlage oder aber eine abweichende Beurteilung vorliegt, tatsächlichen Charakter. Rechtlicher Natur ist hingegen, welchen Anforderungen der (gutachtliche) Beweis einer solchen Feststellung gerecht werden muss. Dementsprechend ist letztinstanzlich frei überprüfbar, ob die vorinstanzliche Beweiswürdigung diese beweisrechtlichen Vorgaben beachtet.
5.2 Die nach <ref-law> zu überprüfende Invalidenrente wurde dem Versicherten mit Verfügung vom 10. Juni 2000 infolge eines psychischen Leidens zugesprochen; die organischen Befunde spielten nur eine untergeordnete Bedeutung und schränkten die Arbeitsfähigkeit nicht ein. Die psychische Beeinträchtigung stand auch im angefochtenen vorinstanzlichen Entscheid im Zentrum, mit dem die strittige Revisionsverfügung vom 15. Oktober 2009 bestätigt wurde.
5.2.1 Die Ärzte der Psychiatrischen Klinik des Spitals Y._ diagnostizierten im IV-Arztbericht vom 23. Juli 1999 eine anhaltende somatoforme Schmerzstörung sowie eine Anpassungsstörung bei multiplen psychosozialen Belastungen und gaben an, ihres Erachtens müsse mit einer andauernden Arbeitsunfähigkeit gerechnet werden.
5.2.2 Im Rahmen des Revisionsverfahrens diagnostizierten die psychiatrischen Gutachter des Medizinischen Abklärungszentrums X._ am 10. April 2009 beim Versicherten ohne Auswirkungen auf die Arbeitsfähigkeit eine Anpassungsstörung mit längerer depressiver Reaktion (ICD-10: F43.21). Vor dem Hintergrund der aktuellen Untersuchungsergebnisse könne die Diagnose einer anhaltenden somatoformen Schmerzstörung nicht bestätigt werden. Die vorherrschenden Beschwerden müssten bei dieser Diagnose entsprechend der ICD-Kriterien neben einem andauernden, schweren und quälenden Schmerz über drei bis sechs Monate, der durch einen physiologischen Prozess oder eine körperliche Störung nicht vollständig erklärt werden könne, unter anderem ein emotionaler Konflikt und psychosoziale Belastungsfaktoren sein, die schwerwiegend genug sein sollten, um als entscheidende ursächliche Faktoren gelten zu können. Diese Kriterien würden vom Versicherten zwar teilweise erfüllt. Es ergäben sich jedoch neben den psychosozialen Belastungsfaktoren keine Hinweise auf relevante innerseelische Konflikte, auch ein schwerer und quälender Schmerz sei nicht spürbar. Anamnestisch sei eine auffällige prämorbide Persönlichkeitsstruktur oder psychiatrische Komorbidität (Persönlichkeitsstörungen, Suchtproblematik, hirnorganische Beeinträchtigungen) nicht zu eruieren.
5.2.2 Im Rahmen des Revisionsverfahrens diagnostizierten die psychiatrischen Gutachter des Medizinischen Abklärungszentrums X._ am 10. April 2009 beim Versicherten ohne Auswirkungen auf die Arbeitsfähigkeit eine Anpassungsstörung mit längerer depressiver Reaktion (ICD-10: F43.21). Vor dem Hintergrund der aktuellen Untersuchungsergebnisse könne die Diagnose einer anhaltenden somatoformen Schmerzstörung nicht bestätigt werden. Die vorherrschenden Beschwerden müssten bei dieser Diagnose entsprechend der ICD-Kriterien neben einem andauernden, schweren und quälenden Schmerz über drei bis sechs Monate, der durch einen physiologischen Prozess oder eine körperliche Störung nicht vollständig erklärt werden könne, unter anderem ein emotionaler Konflikt und psychosoziale Belastungsfaktoren sein, die schwerwiegend genug sein sollten, um als entscheidende ursächliche Faktoren gelten zu können. Diese Kriterien würden vom Versicherten zwar teilweise erfüllt. Es ergäben sich jedoch neben den psychosozialen Belastungsfaktoren keine Hinweise auf relevante innerseelische Konflikte, auch ein schwerer und quälender Schmerz sei nicht spürbar. Anamnestisch sei eine auffällige prämorbide Persönlichkeitsstruktur oder psychiatrische Komorbidität (Persönlichkeitsstörungen, Suchtproblematik, hirnorganische Beeinträchtigungen) nicht zu eruieren.
5.3 5.3.1 Zur Frage, ob sich der Gesundheitszustand des Versicherten seit der ursprünglichen Rentenzusprache vom 10. Juni 2000 wesentlich verbesserte, äusserten sich die Gutachter des Medizinischen Abklärungszentrums X._ nicht ausdrücklich. Zum Beginn und dem Verlauf der Arbeitsunfähigkeit gaben sie an, am Gesundheitszustand des Versicherten habe sich seit 2007 (Zeitpunkt des Gutachtens von Dr. med. T._, der noch eine leichte Depression feststellte) nichts geändert, sodass angenommen werden könne, dass das aktuell ermittelte Belastungsprofil seit 2007 besteht bzw. dass der Versicherte seither wieder zu 100 % arbeitsfähig sei. Zum Zeitraum vor 2007 nahmen sie nicht Stellung, weil eine retrospektive Beurteilung der Arbeitsfähigkeit vor diesem Zeitpunkt schwierig sei.
Dem Umstand, dass die Gutachter sich lediglich in der Lage sahen, den Gesundheitszustand ab dem Jahr 2007 zu beurteilen, lässt grundsätzlich nicht den Schluss zu, dieser habe sich ab 1999 gebessert. Allerdings ist aus heutiger Sicht der IV-Arztbericht der Psychiatrischen Klinik Y._ vom 23. Juli 1999, der die Grundlage für die ursprünglichen Rentenzusprache bildete, als ungenügend, in den IV-Abklärungsverfahren zum damaligen Zeitpunkt aber durchaus als üblich zu beurteilen. Dieser Bericht enthält kaum Informationen, welche die damals diagnostizierte somatoforme Schmerzstörung begründen könnten. Dies darf jedoch nicht dazu führen, dass es späteren medizinischen Experten nicht mehr möglich ist, eine Verbesserung festzustellen. Damit würde die ursprüngliche Festlegung praktisch perpetuiert. Es ist somit davon auszugehen, dass im Jahr 1999 eine somatoforme Schmerzstörung vorlag, wie von den Ärzten der Psychiatrischen Klinik des Spitals Y._ diagnostiziert wurde, und die entsprechenden Voraussetzungen zur Diagnose dieser Störung gegeben waren. Eine zweifellose Unrichtigkeit der damaligen Abklärungen nach der Sach- und Rechtslage sowie der Rechtspraxis zum Zeitpunkt der ursprünglichen Rentenzusprache (<ref-ruling> E. 3 S. 389 f.; SVR 2008 IV Nr. 53 S. 177, I 803/06) ist zu verneinen. Damit entfällt die Möglichkeit, mittels Wiedererwägung nach <ref-law> auf die Verfügung vom 10. Juni 2000 zurückzukommen oder eine (zu Unrecht) auf <ref-law> gestützte Revisionsverfügung mit dieser substituierten Begründung zu schützen (vgl. <ref-ruling> E. 2 S. 369). Zur Beurteilung, ob die Revisionsvoraussetzungen erfüllt sind, ist somit der aktuelle gesundheitliche Zustand mit demjenigen einer vorhandenen somatoformen Schmerzstörung mit Auswirkungen auf die Arbeitsfähigkeit im Jahr 1999 zu vergleichen.
5.3.2 Entgegen dem Einwand des Versicherten sind keine Anhaltspunkte ersichtlich, wonach sich die Definition/Diagnose der somatoformen Schmerzstörung seit 1999 geändert hat. Das ICD-10 Klassifikationssystem hat in Bezug auf diese Störung keine Änderung erfahren (vgl. DILLING/MOMBOUR/SCHMIDT, Internationale Klassifikation psychischer Störungen, ICD-10 Kapitel V [F], Klinisch-diagnostische Leitlinien, 2. Aufl. 1993, S. 191 und 7. Aufl. 2010, S. 207). Die Behauptungen des Versicherten sind insofern unbegründet. Im Übrigen hätten die psychiatrischen Gutachter entsprechende Änderungen bei ihrer Beurteilung berücksichtigt. Was sich seither geändert hat, ist die Beachtung der aus rechtlicher Sicht entscheidenden Voraussetzungen zur willentlichen Überwindbarkeit der somatoformen Schmerzstörung (vgl. BGE <ref-ruling>). Die Frage, ob die Umstände, die einer willentlichen Schmerzüberwindung entgegen stehen, hinreichend erheblich und in genügender Intensität vorhanden sind, stellt eine Rechtsfrage dar (<ref-ruling> E. 1.2 S. 66), die nicht von den Medizinern zu beantworten ist. Die Verneinung eines invalidisierenden Gesundheitsschadens liegt vorliegend allerdings nicht in einer Veränderung dieser Umstände seit dem Jahr 1999 begründet. Die Gutachter des Medizinischen Abklärungszentrums X._ verneinten vielmehr bereits das Vorliegen einer somatoformen Schmerzstörung an sich gemäss den entsprechenden Diagnosekriterien. Die Gutachter wiesen auf verschiedene fehlende Kriterien hin und legten begründet dar, weshalb eine somatoforme Schmerzstörung nun nicht mehr diagnostiziert werden könne. Soweit der Versicherte einwenden lässt, es komme nicht auf die Diagnose an, sondern auf die angegebenen Beschwerden und erhobenen Befunde, ergibt sich einerseits aus den Gutachten des Medizinischen Abklärungszentrums X._ und des Dr. med. T._ übereinstimmend, dass die Befunde so gering waren, dass nur noch von einer depressiven Reaktion bzw. einer leichtgradigen depressiven Störung gesprochen werden konnte. Andererseits gab der Versicherte bei der Begutachtung durch das Medizinische Abklärungszentrum X._ zwar subjektiv die gleichen Schmerzen an wie vor der ursprünglichen Rentenzusprache. Im Unterschied zu damals liegen nun aber zahlreiche Inkonsistenzen sowie Tendenzen zur Symptomausweitung und Selbstlimitierung vor, wie die Gutachter des Medizinischen Abklärungszentrums X._ feststellten. Solche sind aus dem IV-Arztbericht der Psychiatrischen Klinik des Spitals Y._ aus dem Jahr 1999 nicht ersichtlich. Eine Verbesserung der Befunde und des Gesundheitszustandes muss daher auch aufgrund dieses Umstandes bejaht werden.
Zusammenfassend ergibt sich, dass die vorinstanzliche Schlussfolgerung, wonach zwischenzeitlich eine invaliditätsrelevante Verbesserung der psychischen Leiden eingetreten sei, kein Bundesrecht verletzt.
6. Die Beschwerde des Versicherten ist daher abzuweisen, während diejenige der IVSTA gutzuheissen ist.
7. Das Verfahren ist kostenpflichtig (Art. 65 Abs. 1 und Abs. 4 lit. a BGG). Die Gerichtskosten werden dem unterliegenden Versicherten auferlegt (<ref-law>). Dem Gesuch um unentgeltliche Rechtspflege (im Sinne der vorläufigen Befreiung von den Gerichtskosten und der unentgeltlichen Rechtsvertretung) kann entsprochen werden, da die entsprechenden Voraussetzungen erfüllt sind (Art. 64 Abs. 1 und 2 BGG; <ref-ruling> E. 4a S. 202). Es wird indessen ausdrücklich auf <ref-law> aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1. Die Verfahren 8C_567/2011 und 8C_616/1011 werden vereinigt.
2. Die Beschwerde der IV-Stelle für Versicherte im Ausland (IVSTA) wird gutgeheissen und der Entscheid des Bundesverwaltungsgerichtes vom 28. Juni 2011 aufgehoben.
3. Die Beschwerde von S._ wird abgewiesen.
4. S._ wird die unentgeltliche Rechtspflege gewährt.
5. Die Gerichtskosten von Fr. 1'000.- werden S._ auferlegt, indes vorläufig auf die Gerichtskasse genommen.
6. Rechtsanwalt Daniel Christe wird als unentgeltlicher Anwalt von S._ bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
7. Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Bundesverwaltungsgericht zurückgewiesen.
8. Dieses Urteil wird den Parteien, dem Bundesverwaltungsgericht und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 3. Januar 2012
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Ursprung
Der Gerichtsschreiber: Kathriner