Sachverhalt:
A.
Der 1968 geborene A._ bezog ab dem 1. Juli 1996 eine ganze Invalidenrente (Verfügung vom 17. Dezember 2003).
Im Nachgang an die Meldung eines in den Jahren 2008 bis 2010 erzielten Einkommens beauftragte die IV-Stelle Basel-Stadt die Klinik B._ mit einer Begutachtung des Versicherten (Expertise vom 18. März 2014).
Nach dem Eingang einer Denunziation und weiteren Abklärungen liess die IV-Stelle den Versicherten im Zeitraum vom 9. September 2013 bis zum 13. April 2015 durch die C._ AG observieren (Ermittlungsbericht vom 13. Mai 2015). Am 6. Januar 2016 erhob sie Strafanzeige gegen ihn, holte alsdann die Strafakten ein und sistierte die Invalidenrente schliesslich mit Verfügung vom 21. Juli 2016 (bestätigt durch das Urteil des Sozialversicherungsgerichts des Kantons Basel-Stadt vom 22. Februar 2017).
Am 9. Februar 2018 erstattete Prof. Dr. med. D._, Fachärztin für Psychiatrie und Psychotherapie, im Auftrag der IV-Stelle ihr Gutachten. Nach durchgeführtem Vorbescheidverfahren hob die IV-Stelle die rentenzusprechende Verfügung vom 17. Dezember 2003 mit Verfügung vom 24. Mai 2019 revisionsweise auf. Am 24. September 2019 verfügte sie sodann eine Rückforderung im Umfang von Fr. 77'438.- für zwischen Mai 2014 und Juli 2016 ausgerichtete Leistungen.
B.
Die gegen die Verfügungen vom 24. Mai und 24. September 2019 erhobenen Beschwerden beurteilte das Sozialversicherungsgericht des Kantons Basel-Stadt in zwei separaten Verfahren. Mit dem Urteil vom 9. Dezember 2020 im Verfahren IV.2019.118 hiess es die Beschwerde gegen die Renteneinstellung teilweise gut und änderte die angefochtene Verfügung vom 24. Mai 2019 dahingehend ab, dass es einen Rentenanspruch ab dem 21. Juli 2016 verneinte. Im Übrigen wies es die Beschwerde ab. Mit Urteil vom gleichen Tag im Verfahren IV.2019.164 hob es sodann die Verfügung vom 24. September 2019 auf.
C.
Die IV-Stelle erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit folgenden Rechtsbegehren:
"1. Es sei das Urteil des Sozialversicherungsgerichts Basel-Stadt IV.2019.164 vom 9. Dezember 2020 aufzuheben und die Verfügung vom 24. September 2019 sei zu bestätigen.
2. Eventualiter sei die Angelegenheit an die Vorinstanz zur Prüfung der Rückforderungsvoraussetzungen nach Art. 88bis Abs. 2 lit. b IVV zurückzuweisen."
In ihrer Vernehmlassung vom 21. September 2021 ersucht die Vorinstanz um Abweisung der Beschwerde. Mit Eingabe vom 20. Oktober 2021 beantragt der Beschwerdegegner ebenfalls die Abweisung, soweit auf die Beschwerde einzutreten sei. Sodann ersucht er um Gewährung der unentgeltlichen Rechtspflege. Das Bundesamt für Sozialversicherungen (BSV) verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Die Beschwerdeschrift hat unter anderem ein Rechtsbegehren zu enthalten (Art. 42 Abs. 1 BGG). Das Begehren umschreibt den Umfang des Rechtsstreits und muss grundsätzlich so formuliert werden, dass es bei Gutheissung zum Urteil erhoben werden kann. Da die Beschwerde an das Bundesgericht ein reformatorisches Rechtsmittel ist (Art. 107 Abs. 2 BGG), darf sich diese grundsätzlich nicht darauf beschränken, die Aufhebung bzw. Rückweisung des angefochtenen Entscheids zu beantragen, sondern muss einen Antrag in der Sache stellen. Der Beschwerdeführer hat demnach anzugeben, welche Punkte des Entscheids angefochten und welche Abänderung des Dispositivs beantragt werden. Grundsätzlich ist ein materieller Antrag erforderlich, damit die Beschwerde zulässig ist, ausser wenn das Bundesgericht ohnehin nicht reformatorisch entscheiden könnte (<ref-ruling> E. 1.3; <ref-ruling> E. 1.2; <ref-ruling> E. 1.3; <ref-ruling> E. 3.1: siehe allerdings auch <ref-ruling> E. 1.4.1).
Rechtsbegehren sind nach Treu und Glauben auszulegen, insbesondere im Lichte der dazu gegebenen Begründung (<ref-ruling> E. 1; Urteil 4P.266/2006 vom 13. Dezember 2006 E. 1.3). Nach der Rechtsprechung schadet eine sichtlich ungewollte oder unbeholfene Wortwahl der am Recht stehenden Person ebenso wenig wie eine nicht geglückte oder rechtsirrtümliche Ausdrucksweise. Es genügt, wenn der Beschwerde insgesamt entnommen werden kann, was die beschwerdeführende Person verlangt (SVR 2004 IV Nr. 25 S. 75, I 138/02 E. 3.2.1 mit Hinweisen).
1.2. Zwar spricht die Beschwerdeführerin in der Antrags-Ziffer 1. einzig von der Aufhebung des vorinstanzlichen Urteils im Verfahren IV.2019.164 und Bestätigung der Verfügung vom 24. September 2019. In Antrags-Ziffer 2. ersucht sie jedoch eventualiter um die Rückweisung der Sache an das kantonale Gericht "zur Prüfung der Rückforderungsvoraussetzungen nach Art. 88bis Abs. 2 lit. b IVV" und weist damit zumindest implizit auf die Voraussetzungen für die Herabsetzung respektive Aufhebung einer Invalidenrente hin. In ihrer Begründung wendet sich die Beschwerdeführerin sodann deutlich gegen den vorinstanzlich festgesetzten Zeitpunkt einer uneingeschränkten Arbeitsfähigkeit per 21. Juli 2016 mit konsekutiver Aufhebung der Invalidenrente per dato. Auch legt sie ihrer Beschwerde das diesen Aspekt behandelnde Urteil vom 9. Dezember 2020 im Verfahren IV.2019.118 bei.
Insgesamt ist daher - entgegen der Ansicht des Beschwerdegegners - davon auszugehen, dass die Beschwerdeführerin vorliegend beide vorinstanzlichen Urteile in den Verfahren IV.2019.118 (Rentenaufhebung: 9C_599/2021) und IV.2019.164 (Rückforderung: 9C_333/2021) anfechtet. Weil es um den gleichen Sachverhalt geht und sich weitgehend die nämlichen Rechtsfragen stellen, rechtfertigt es sich, die beiden Verfahren 9C_599/2021 und 9C_333/2021 zu vereinigen und in einem einzigen Urteil zu erledigen (vgl. Art. 71 BGG in Verbindung mit Art. 24 BZP [SR 273]; vgl. <ref-ruling> E. 1.1 mit Hinweis).
2.
Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (Art. 95 lit. a BGG). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). 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 Art. 95 BGG beruht (Art. 105 Abs. 2 BGG).
Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Indes prüft es, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1 mit Hinweis).
3.
3.1. Unbestritten ist die grundsätzliche Zulässigkeit einer rückwirkenden Renteneinstellung (gestützt auf Art. 88bis Abs. 2 lit. b IVV) und (allfälligen) Rückforderung von Rentenbetreffnissen. Streitig und zu prüfen ist (einzig), ob Bundesrecht verletzt wurde, indem die Vorinstanz die Rente erst per 21. Juli 2016 aufgehoben und damit eine Rückforderung zwischen Mai 2014 und Juli 2016 verneint hat (Art. 107 Abs. 1 BGG; <ref-ruling> E. 2.1; <ref-ruling> E. 2.5; Urteil 9C_756/2009 vom 8. Februar 2010 E. 4.1; ferner JOHANNA DORMANN, in: Basler Kommentar, Bundesgerichtsgesetz, 3. Aufl. 2018, N. 2 zu Art. 107 BGG).
3.2.
3.2.1. In den angefochtenen Urteilen wurden die massgeblichen rechtlichen Grundlagen und die einschlägige bundesgerichtliche Rechtsprechung zutreffend dargelegt. Es betrifft dies namentlich die Erwägungen zum Rentenanspruch (Art. 28 Abs. 2 IVG) und zur Beweiskraft medizinischer Berichte und Gutachten (<ref-ruling> E. 3a und 3b), insbesondere im Zusammenhang mit der Würdigung von Observationsergebnissen (Urteil 9C_395/2016 vom 25. August 2016 E. 4.2.1 mit Hinweisen). Darauf wird verwiesen.
3.2.2. Anzufügen ist, dass es sich bei den gerichtlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit grundsätzlich um lediglich unter eingeschränktem Blickwinkel überprüfbare Tatfragen handelt. Gleiches gilt für die konkrete Beweiswürdigung (<ref-ruling> E. 2.4 mit Hinweis; Urteil 9C_463/2020 vom 17. Dezember 2020 E. 2.2).
Eine Beweiswürdigung ist unter anderem dann offensichtlich unrichtig, wenn das Gericht auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (vgl. <ref-ruling> E. 2.3; <ref-ruling> E. 4.2; <ref-ruling> E. 4.2).
4.
4.1. Das kantonale Gericht hat das Material aus der zwischen September 2013 und April 2015 erfolgten Observation des Beschwerdegegners als verwertbar erachtet. Hinsichtlich der Beweiskraft des Gutachtens von Prof. Dr. med. D._ vom 9. Februar 2018 hat es darauf geschlossen, dass sich die Gutachterin zu wenig mit den echtzeitlichen Vorberichten und dem Gutachten der Klinik B._ vom 18. März 2014 (die eine Erkrankung aus dem schizophrenen Formenkreis diagnostiziert hatten) auseinandergesetzt und begründet habe, weshalb sich diese geirrt haben sollten. Die Einschätzung der Expertin, wonach im Begutachtungszeitpunkt keine Erkrankung aus dem schizophrenen Formenkreis mehr vorgelegen habe, sei jedoch schlüssig.
Die Observationsvideos und der Umfang der Strafakten zeigten darüber hinaus eindrücklich auf, dass beim Beschwerdegegner in den Jahren 2014 und 2015 zunehmend ein Funktionsniveau bestanden habe, welches sich mit einer schwerwiegenden Diagnose einer paranoiden Schizophrenie nicht vereinbaren lasse.
Somit sei festzustellen, dass das Gutachten von Prof. Dr. med. D._ vom 9. Februar 2018, welches auf der Untersuchung vom 21. September 2017 beruhe, in Bezug auf die rückwirkend vorgenommene Einschätzung, wonach beim Beschwerdegegner bereits ab Anfang der 2000er Jahre keinerlei psychiatrische Erkrankung vorgelegen haben solle, nicht hinreichend begründet erscheine. Abgesehen davon könne es für vollumfänglich beweiskräftig angesehen werden.
Im Ergebnis sei für den rückwirkenden Zeitraum auf die Berichte und Feststellungen der behandelnden Ärzte sowie der Gutachter der Klinik B._ abzustellen, welche dem Beschwerdegegner eine volle Arbeitsunfähigkeit bescheinigt hätten. Aufgrund der deliktischen Handlungen sowie der Observationen in den Jahren 2014 und 2015 sei jedoch davon auszugehen, dass - auch wenn der genaue Zeitpunkt der gesundheitlichen Verbesserung nicht mehr genau nachvollzogen werden könne - jedenfalls ab dem Zeitpunkt der Verfügung vom 21. Juli 2016, womit die Rente des Beschwerdegegners sistiert worden sei, keinerlei Arbeitsunfähigkeit mehr bestanden habe. In Abänderung der Verfügung vom 24. Mai 2019 werde die Invalidenrente daher erst per 21. Juli 2016 aufgehoben. Da sich die Rückforderung der Rentenbetreffnisse lediglich auf einen Zeitraum vor Sistierung der Invalidenrente beziehe, sei die angefochtene Verfügung vom 24. September 2019 aufzuheben.
4.2. Die Beschwerdeführerin rügt die dargelegte Beweiswürdigung mit der Schlussfolgerung einer uneingeschränkten Arbeitsfähigkeit des Beschwerdegegners (erst) per 21. Juli 2016.
5.
5.1. Die vorinstanzliche Feststellung, wonach sich Prof. Dr. med. D._ nicht im Einzelnen mit den echtzeitlichen Berichten auseinandergesetzt und nachvollziehbar begründet hat, inwiefern sich die behandelnden Ärzte geirrt hätten, erscheint für den Zeitraum vor der Überwachung des Beschwerdegegners ab Herbst 2013 mit Blick auf die gutachterlichen Ausführungen nicht offensichtlich unrichtig. Die entsprechende Schlussfolgerung des kantonalen Gerichts, wonach die gutachterliche Einschätzung, dass bereits ab Anfang der 2000er Jahre keinerlei psychiatrische Erkrankung vorgelegen haben solle, nicht hinreichend begründet erscheine, ist daher nicht willkürlich. Entsprechendes wird auch nicht substanziiert gerügt.
5.2. Hinsichtlich der Würdigung der Erkenntnisse aus der ab Herbst 2013 erfolgten Observation ist das kantonale Gericht sodann Prof. Dr. med. D._ gefolgt. Es hat festgestellt, die Expertin habe zu Recht festgehalten, dass der Beschwerdegegner weder beim Führen eines Fahrzeugs im Strassenverkehr noch im Umgang mit anderen Menschen Auffälligkeiten gezeigt habe, welche in die Richtung einer paranoiden Schizophrenie deuten würden. Vielmehr hätten die Aufnahmen einen regen Austausch mit anderen Männern durch intakte Modulationsfähigkeit in Form von Überzeugungsarbeit, Blickkontakt und Gestik dokumentiert. Insgesamt sei der Beschwerdegegner durch einen konzentrierten und vital-dynamischen Eindruck aufgefallen. In die gleiche Richtung würden die von der Gutachterin gemachten Ausführungen zum "Aktenauszug inklusive der Unterlagen der Staatsanwaltschaft" hinweisen, die sie auf zwei Seiten zitiere. Auch der Umstand, dass nach der Medikamenteneinnahme am Tag der Begutachtung der Spiegel am selben Morgen unter dem therapeutischen Bereich gelegen habe, spreche gegen die Diagnose einer paranoiden Schizophrenie.
Trotz dieser Feststellungen ist das kantonale Gericht (entgegen der Gutachterin) für den Zeitraum ab Beginn der Observation im Herbst 2013 weiterhin vom Vorliegen funktioneller Einschränkungen aufgrund einer paranoiden Schizophrenie ausgegangen und zwar bis zum 21. Juli 2016. Diese Schlussfolgerung steht im Widerspruch zu den dargelegten Feststellungen und ist daher unhaltbar (vgl. E. 2 und 3.2.2 hiervor). Daran ändert der Umstand nichts, dass Prof. Dr. med. D._ sich allenfalls nicht eingehend mit dem Vorgutachten der Klinik B._ vom 18. März 2014 auseinandergesetzt hat. Dieses Gutachten erging in Unkenntnis der (unbestritten verwertbaren) Observationserkenntnisse und damit der vollständigen Aktenlage, weshalb ihm keine Beweiskraft zukommt.
Gestützt auf die dargelegten Feststellungen, gemäss denen das observierte Verhalten des Versicherten mit einer schwerwiegenden psychischen Störung unvereinbar ist (Gutachten vom 9. Februar 2018, S. 32), ist konsequenterweise davon auszugehen, dass ab Beginn der Überwachung des Beschwerdegegners am 9. September 2013 keine Funktionseinschränkungen mehr bestanden. Die Rentenaufhebung ist somit ab diesem Zeitpunkt gerechtfertigt. Die Verfügung vom 24. September 2019 ist dagegen zu bestätigen.
6.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdegegner grundsätzlich die Gerichtskosten zu tragen (Art. 66 Abs. 1 Satz 1 und Art. 68 Abs. 1 BGG). Seinem Gesuch um unentgeltliche Rechtspflege (Prozessführung und Verbeiständung) kann jedoch entsprochen werden (Art. 64 Abs. 1 und 2 BGG). Es wird indessen ausdrücklich auf Art. 64 Abs. 4 BGG hingewiesen, wonach die begünstigte Partei der Bundesgerichtskasse Ersatz zu leisten hat, wenn sie später dazu in der Lage ist. Die Sache ist zur Neuverlegung der Kosten und Parteientschädigung des vorangegangenen Verfahrens an die Vorinstanz zurückzuweisen (Art. 68 Abs. 5 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Das Urteil des Sozialversicherungsgerichts des Kantons Basel-Stadt vom 9. Dezember 2020 im Verfahren IV.2019.118 wird insoweit präzisiert, als die Verfügung vom 24. Mai 2019 dahingehend abgeändert wird, dass der Rentenanspruch des Beschwerdegegners per 9. September 2013 aufgehoben wird. Das Urteil des Sozialversicherungsgericht des Kantons Basel-Stadt vom 9. Dezember 2020 im Verfahren IV.2019.164 wird aufgehoben und die Verfügung der IV-Stelle Basel-Stadt vom 24. September 2019 bestätigt.
2.
Dem Beschwerdegegner wird die unentgeltliche Rechtspflege gewährt und Advokat Dr. Yves Waldmann als unentgeltlicher Anwalt bestellt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdegegner auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Dem Rechtsvertreter des Beschwerdegegners wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 2800.- ausgerichtet.
5.
Die Sache wird zur Neuverlegung der Kosten und Parteientschädigung des vorangegangenen Verfahrens an das Sozialversicherungsgericht des Kantons Basel-Stadt zurückgewiesen.
6.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Basel-Stadt und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 14. Dezember 2021
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Parrino
Die Gerichtsschreiberin: Nünlist