Sachverhalt:
A.
Der 1963 geborene A._ meldete sich mit Gesuch vom Dezember 1997 bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle des Kantons Zürich liess ihn durch das Zentrum für Medizinische Begutachtung (ZMB), Basel, begutachten (Expertise vom 11. Februar 1999) und sprach ihm mit Verfügung vom 14. Oktober 1999 ab dem 1. Juni 1998 eine ganze Invalidenrente zu (Invaliditätsgrad: 71 %). In den darauf folgenden Jahren bestätigte die Verwaltung jeweils mit Mitteilungen den unveränderten Anspruch des Versicherten auf eine ganze Rente.
Im Rahmen eines im Jahr 2015 eingeleiteten Revisionsverfahrens veranlasste die IV-Stelle bei der Academy of Swiss Insurance Medicine (asim), Universitätsspital Basel, eine polydisziplinäre Begutachtung (Expertise vom 19. Juli 2016). Nach durchgeführtem Vorbescheidverfahren setzte die Verwaltung die bisherige ganze Rente des A._ auf den 1. Juli 2017 auf eine halbe Invalidenrente herab (Invaliditätsgrad: 55 %; Verfügung vom 3. Mai 2017).
B.
Die dagegen erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 29. November 2018 gut und hob die Verfügung vom 3. Mai 2017 auf.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt die IV-Stelle die Aufhebung des kantonalen Erkenntnisses und die Rückweisung der Sache an die Vorinstanz zur neuen Entscheidung.
A._ schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Sozialversicherungen (BSV) beantragt deren Gutheissung.

Erwägungen:
1.
1.1. Das Bundesgericht prüft die Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (<ref-law>; <ref-ruling> E. 1 S. 44 mit Hinweisen). Da die Beschwerde an das Bundesgericht ein reformatorisches Rechtsmittel ist (<ref-law>), muss auch das Rechtsbegehren grundsätzlich reformatorisch gestellt werden; ein blosser Antrag auf Aufhebung bzw. Rückweisung des angefochtenen Entscheids ist nicht zulässig, ausser wenn das Bundesgericht ohnehin nicht reformatorisch entscheiden könnte (<ref-ruling> E. 1.3 S. 317; <ref-ruling> E. 1.2 S. 135; <ref-ruling> E. 1.3 S. 383; <ref-ruling> E. 3.1 S. 489 f.). Bei der Beurteilung, ob die Beschwerdeschrift ein hinreichendes Begehren enthält, darf das Bundesgericht indessen nicht ausschliesslich auf den am Anfang oder am Ende der Rechtsschrift förmlich gestellten Antrag abstellen. Vielmehr kann sich das Begehren auch aus der Begründung oder aus der Begründung zusammen mit dem formellen Antrag ergeben (BGE <ref-ruling> E. 1.2 S. 135 f.; Urteil 9C_671/2014 vom 30. Januar 2015 E. 2.1, in: SVR 2015 BVG Nr. 55 S. 234).
1.2. Die IV-Stelle beantragt die Aufhebung des kantonalen Entscheids sowie die Rückweisung der Sache an die Vorinstanz zur umfassenden, "allseitigen" Prüfung ohne Bindung an frühere Beurteilungen. Daraus ist zu entnehmen, dass die Beschwerdeführerin mit der Weiterausrichtung der ganzen Rente nicht einverstanden ist und eine Rentenherabsetzung anstrebt, weshalb auf die Beschwerde einzutreten ist.
2.
2.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten 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 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 (<ref-law>). 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 (<ref-law>).
2.2. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Pflicht zur Begründung 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 S. 236 mit Hinweisen).
3.
Streitig und zu prüfen ist, ob die Vorinstanz Bundesrecht verletzte, indem sie die Rentenherabsetzungsverfügung der IV-Stelle vom 3. Mai 2017 aufhob.
Das kantonale Gericht legte die massgeblichen Rechtsgrundlagen zutreffend dar. Es betrifft dies namentlich die Bestimmungen und Grundsätze zur Erwerbsunfähigkeit (<ref-law>) und zur Invalidität (<ref-law>), zum Rentenanspruch (<ref-law>) sowie zur Rentenrevision (<ref-law>; <ref-ruling> E. 2.3 S. 10 f.; <ref-ruling> E. 3 S. 132 f.; <ref-ruling> E. 4b S. 200). Darauf wird verwiesen.
4.
4.1. In Bezug auf die Entwicklung des Sachverhalts seit der Rentenzusprache vom 14. Oktober 1999 stellte die Vorinstanz insbesondere in Anlehnung an das asim-Gutachten vom 19. Juli 2016 fest, der Gesundheitszustand habe sich somatisch zwar verschlechtert. Das Vorliegen eines Revisionsgrundes sei aber dennoch zu verneinen. Denn liege in einem Fall wie dem vorliegenden eine Veränderung ausschliesslich in Form einer gesundheitlichen Verschlechterung vor, könne eine Reduktion oder eine Aufhebung der Rente auch bei Qualifikation der Verschlechterung als Revisionsgrund nur dann zulässig sein, wenn sich die ursprüngliche Zusprechung der Rente beziehungsweise der Rente in der bisherigen Höhe im Sinne der Voraussetzungen der Wiedererwägung als zweifellos unrichtig erweise.
Das Sozialversicherungsgericht erwog im Weiteren, eine Herabsetzung der bisherigen ganzen Rente des Beschwerdegegners falle demnach selbst bei Zulassung der zur Diskussion stehenden gesundheitlichen Verschlechterung als Revisionsgrund nur dann in Betracht, wenn die Voraussetzungen für eine Wiedererwägung - also zweifellose Unrichtigkeit und erhebliche Bedeutung der Berichtigung - der rentenzusprechenden Verfügung vom 14. Oktober 1999 gegeben seien, was verneint werde. Es könne daher offen bleiben, ob die gesundheitliche Verschlechterung überhaupt als Revisionsgrund tauge, ungeachtet dessen, dass sie nicht dazu geeignet sei, für sich allein zu einer Senkung des Invaliditätsgrades unter den Schwellenwert einer ganzen Rente zu führen. Somit verbiete sich eine Herabsetzung der damals zugesprochenen Rente.
4.2. Die Beschwerdeführerin und das BSV sind der Auffassung, dass mit der im Vergleich zum Zeitpunkt der Rentenzusprache eingetretenen Verschlechterung des somatischen Gesundheitszustands ein Revisionsgrund ausgewiesen sei. Entsprechend müsse der Rentenanspruch umfassend und ohne Bindungen an frühere Beurteilungen neu geprüft werden. Die Ausführungen der Vorinstanz, wonach eine Verschlechterung nur dann als Revisionsgrund zugelassen werde, wenn die Wiedererwägungsvoraussetzungen gegeben seien, entbehre einer gesetzlichen Grundlage und lasse sich auch nicht aus der bundesgerichtlichen Rechtsprechung ableiten.
5.
5.1. Die vorinstanzlichen Feststellungen betreffend die Gesundheitsverschlechterung (E. 4.1) werden von den Parteien nicht bestritten; sie sind für das Bundesgericht verbindlich (E. 2.1). Zu prüfen ist die Rechtsfrage, ob mit dem verschlechterten Gesundheitszustand ein Revisionsgrund im Sinne von <ref-law> vorliegt.
5.2.
5.2.1. Voraussetzung für eine Rentenrevision bildet die Änderung des Invaliditätsgrades einer rentenbeziehenden Person in einer für den Anspruch erheblichen Weise (<ref-law>). Anlass zur Rentenrevision gibt jede wesentliche Änderung in den tatsächlichen Verhältnissen seit Zusprechung der Rente, die geeignet ist, den Invaliditätsgrad und damit den Anspruch zu beeinflussen. Für eine Rentenanpassung genügt daher nicht bereits irgendeine Veränderung im Sachverhalt. Eine hinzugetretene oder weggefallene Diagnose stellt somit nicht per se einen Revisionsgrund dar, da damit das quantitative Element der (erheblichen) Gesundheitsverbesserung oder -verschlechterung nicht zwingend ausgewiesen ist. Eine weitere Diagnosestellung bedeutet nur dann eine revisionsrechtlich relevante Gesundheitsverschlechterung oder eine weggefallene Diagnose eine verbesserte gesundheitliche Situation, wenn diese veränderten Umstände den Rentenanspruch berühren (<ref-ruling> E. 5.2 S. 12 f. mit Hinweisen).
5.2.2. Nach dem Gesagten (E. 5.2.1) kann wohl, wie die Beschwerdeführerin und das BSV zu Recht konstatieren, nicht nur eine (erhebliche) Gesundheitsverbesserung, sondern grundsätzlich auch eine gesundheitliche Verschlechterung revisionsrechtlich relevant sein und zu einer allseitigen, umfassenden Neubeurteilung des Rentenanspruchs führen. Die gesundheitliche Situation hat sich aber nur dann in anspruchsrelevanter Weise verbessert oder verschlechtert, wenn die veränderten Umstände den Rentenanspruch berühren. An einem Revisionsgrund nach <ref-law> mangelt es daher beispielsweise, wenn die Sachverhaltsänderung lediglich in einer Reduktion oder Erhöhung des erwerblichen Arbeitspensums liegt und dieser Umstand für sich allein nicht anspruchsrelevant ist (<ref-ruling> E. 2.3 S. 10 und E. 5.2 S. 12 f. mit Hinweis).
5.3.
5.3.1. Die Vorinstanz kam, wie bereits erwähnt (E. 4.1), verbindlich zum Schluss, seit Erlass der Verfügung vom 14. Oktober 1999 habe sich der Gesundheitszustand somatisch verschlechtert. Voraussetzung dafür, dass aus dieser Sachverhaltsänderung ein Revisionsgrund abgeleitet werden kann, ist die Geeignetheit dieser Änderung, den Invaliditätsgrad und damit den Anspruch zu beeinflussen.
5.3.2. Im vorliegenden Fall gab die Gesundheitsverschlechterung von vornherein keinen Anlass zur Rentenrevision: Besteht bereits ein Anspruch auf eine ganze Rente (hier: Invaliditätsgrad von 71 %), ist deren Erhöhung rechtlich ausgeschlossen; eine weitere gesundheitliche Verschlechterung kann daher in einem solchen Fall von vornherein entgegen der Beschwerdeführerin gerade nicht geeignet sein, den Rentenanspruch zu beeinflussen (vgl. Urteile 9C_107/2019 vom 7. August 2019 E. 5.2.3; 8C_405/2017 vom 7. November 2017 E. 4.3; 9C_309/2016 vom 13. September 2016 E. 3.4.2.1). Es besteht mithin kein Raum für eine revisionsweise Rentenaufhebung. Eine andere anspruchsrelevante Veränderung des Sachverhalts im massgeblichen Vergleichszeitraum ist nicht ersichtlich und wird auch nicht geltend gemacht. Bei diesem Ergebnis braucht auf die weiteren Erwägungen der Vorinstanz, wonach eine Verschlechterung in einem Fall wie dem vorliegenden nur dann als Revisionsgrund gelten könne, wenn die Wiedererwägungsvoraussetzungen gegeben seien (E. 4.1 oben), nicht weiter eingegangen zu werden. Die Frage kann vielmehr offen gelassen werden.
6.
Die Verneinung der Wiedererwägungsvoraussetzungen als solche im Rahmen der substituierten Begründung ist von der Beschwerdeführerin unangefochten geblieben, weshalb sich Weiterungen erübrigen. Die Beschwerde ist unbegründet. Damit bleibt es beim kantonalen Entscheid.
7.
Dem Ausgang des Verfahrens entsprechend hat die Beschwerdeführerin die Gerichtskosten zu tragen (<ref-law>) und dem Beschwerdegegner eine Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'400.- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich, dem Bundesamt für Sozialversicherungen und der AXA Stiftung Berufliche Vorsorge, Winterthur, schriftlich mitgeteilt.
Luzern, 16. August 2019
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Meyer
Die Gerichtsschreiberin: Huber