Faits :
A.
A._ est propriétaire de la parcelle n° 7'399 de la Commune de Montreux depuis 2011, dont la partie est est colloquée en zone à bâtir dite de résidence d'agrément et sa partie ouest en zone agricole.
Le 6 novembre 1996, la commune avait octroyé aux précédents propriétaires une autorisation de construire sur la partie sud-ouest de la parcelle un garage - réalisé en 1997 - conformément aux formulaire et plan de situation de la demande. Ces documents indiquaient que le garage était situé dans la zone de résidence d'agrément.
A l'occasion d'une demande de permis de construire sans lien avec le présent litige, le Service vaudois du développement territorial (SDT) a constaté qu'un garage semi-enterré construit en 1997 était situé hors de la zone à bâtir alors qu'aucune autorisation cantonale n'avait été délivrée.
B.
Par décision du 10 mai 2016, le SDT a ordonné la remise en état des lieux, à savoir le démontage du garage et l'évacuation des matériaux vers une installation ad hoc ainsi que le rétablissement et le réensemencement du terrain naturel. Un délai au 30 septembre 2016 a été imparti à l'intéressé pour ce faire.
Statuant sur recours de A._, la Cour de droit administratif et public du Tribunal cantonal vaudois (CDAP) a annulé cette décision par arrêt du 15 mars 2018.
C.
Agissant par la voie du recours en matière de droit public, le canton de Vaud, par la Cheffe du Département du territoire et de l'environnement, demande au Tribunal fédéral d'annuler l'arrêt cantonal, la décision du SDT étant confirmée et un nouveau délai de trois mois étant accordé à A._ pour s'y conformer. Subsidiairement, il demande le renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants.
La cour cantonale renonce à se déterminer et se réfère aux considérants de son arrêt. La commune s'en remet à justice. L'intimé se détermine et conclut au rejet du recours dans la mesure de sa recevabilité. Consulté, l'Office fédéral du développement territorial (ARE) conclut à l'admission du recours. L'intimé se détermine encore et maintient ses conclusions.
Par ordonnance du 16 mai 2018, le Président de la Ire Cour de droit public a rejeté la requête d'effet suspensif présentée par le recourant.

Considérant en droit :
1.
Rendu en dernière instance cantonale (art. 86 al. 1 let. d LTF), dans une cause de droit public (<ref-law>), l'arrêt attaqué peut en principe faire l'objet d'un recours en matière de droit public, aucune des exceptions figurant à l'<ref-law> n'étant réalisée.
Selon l'art. 89 al. 2 let. d LTF, ont qualité pour recourir les personnes, organisations et autorités auxquelles une autre loi fédérale accorde un droit de recours. Tel est le cas de l'art. 34 al. 2 let. c LAT qui permet aux cantons et aux communes de recourir à l'encontre des autorisations visées aux art. 24 à 24d LAT, à savoir pour des constructions sises, comme en l'espèce, hors zone à bâtir.
Les autres conditions de recevabilité sont réunies, si bien qu'il convient d'entrer en matière.
2.
Aucune construction ou installation ne peut être créée ou transformée sans autorisation de l'autorité compétente (art. 22 al. 1 LAT). Pour tous les projets de construction situés hors de la zone à bâtir, c'est l'autorité cantonale compétente qui décide si ceux-ci sont conformes à l'affectation de la zone ou si une dérogation peut être accordée (art. 25 al. 2 LAT). En l'espèce, il est constant que le garage litigieux est construit sur la part de la parcelle colloquée en zone non constructible. L'autorisation délivrée par l'autorité communale pour une construction hors zone à bâtir est dès lors nulle.
Pour qu'une autorisation hors de la zone à bâtir soit délivrée, la construction ou l'installation doit soit être conforme à l'affectation de la zone (art. 22 al. 2 let. a LAT), soit remplir les conditions des exceptions prévues aux 24 ss LAT.
Dans son recours, le département cantonal fait valoir une violation du principe de la séparation du bâti et du non-bâti à titre général et du "droit dérogatoire fédéral" au sens des art. 24 ss LAT en particulier. En l'occurrence, il n'est pas contesté que la construction n'est pas conforme à l'affectation de la zone agricole et qu'aucune exception légale ne permet d'autoriser la construction litigieuse, de sorte qu'aucun permis de construire ne peut être accordé a posteriori.
3.
Le canton recourant conteste dès lors l'annulation de l'ordre de remise en état prononcée par la CDAP tandis que l'intimé estime cette annulation bien fondée en raison du principe de la bonne foi.
3.1. Lorsque des constructions ou des installations illicites sont réalisées en dehors de la zone à bâtir, le droit fédéral exige en principe que soit rétabli un état conforme au droit. Le principe de la séparation de l'espace bâti et non bâti, qui préserve différents intérêts publics, est de rang constitutionnel; il fait partie intégrante de la notion d'utilisation mesurée du sol de l'art. 75 al. 1 Cst. (cf. Message du Conseil fédéral du 20 janvier 2010 relatif à une révision partielle de la LAT, FF 2010 964 ch. 1.2.1 et 973 ch. 2.1; arrêts 1C_176/2016 du 10 mai 2017 consid. 7.1; 1C_109/2014 du 4 mars 2015 consid. 6.5; RUDOLF MUGGLI, Commentaire pratique LAT: construire hors zone à bâtir, 2017, n. 1 et 16 ad remarques préliminaires relatives aux art. 24 à 24e et 37a LAT; WALDMANN/HÄNNI, Handkommentar RPG, 2006, n. 14 ad art. 1 LAT; BRAHIER/PERRITAZ, LAT révisée, dézonage et indemnisation des propriétaires, 2015, p. 74; cf. également art. 14 al. 2, 16 al. 1, 22 al. 2 let. a et 24 ss LAT). Cette séparation doit par conséquent, en dehors des exceptions prévues par la loi, demeurer d'application stricte (<ref-ruling> consid. 6.4 p. 40; arrêt 1A.301/2000 du 28 mai 2001 consid. 6c publié in ZBl 2002 p. 364). Si des constructions illégales, contraires au droit de l'aménagement du territoire, sont indéfiniment tolérées en dehors de la zone constructible, le principe de la séparation du bâti et du non-bâti est remis en question et un comportement contraire au droit s'en trouve récompensé (arrêt 1C_143/2015 du 13 novembre 2015 consid. 2.4). S'ajoute à cela que la remise en état poursuit encore d'autres intérêts publics, à savoir la limitation du nombre et des dimensions des constructions en zone agricole (cf. <ref-ruling> consid. 6.4 p. 40; <ref-ruling> consid. 6b p. 225; arrêt 1A.301/2000 du 28 mai 2001 consid. 6c in ZBl 2002 p. 364) ainsi que le respect du principe de l'égalité devant la loi (arrêt 1C_276/2016 du 2 juin 2017 consid. 3.3).
C'est pourquoi, en règle générale, les constructions érigées sans droit en zone agricole doivent être supprimées, à moins que - à titre exceptionnel - l'écart constaté par rapport à ce qu'admet le droit se révèle mineur et qu'une remise en état ne soit pas dans l'intérêt public. La jurisprudence réserve encore les situations dans lesquelles le bénéficiaire de l'autorisation de construire frappée de nullité pouvait de bonne foi se croire autorisé à construire (<ref-ruling> consid. 6 p. 364 s.; <ref-ruling> consid. 6 p. 35).
Découlant directement de l'art. 9 Cst. et valant pour l'ensemble de l'activité étatique, le principe de la bonne foi protège le citoyen dans la confiance légitime qu'il met dans les assurances reçues des autorités, lorsqu'il a réglé sa conduite d'après des décisions, des déclarations ou un comportement déterminé de l'administration (<ref-ruling> consid. 3.6.3 p. 193; <ref-ruling> consid. 2.5.1 p. 73; <ref-ruling> consid. 6.1 p. 636 s.). Une particularité du droit à la protection de la bonne foi consiste dans le fait qu'il peut, le cas échéant, contraindre l'autorité à prendre une décision contraire à la loi (AUER/MALINVERNI/HOTTELIER, Droit constitutionnel suisse vol. II - les droits fondamentaux, 3e éd. 2013, n° 1180, p. 550; arrêts 1C_464/2015 du 14 juin 2016 consid. 2.1; 1C_18/2015 du 22 mai 2015 consid. 3.1.1). Pour que le justiciable puisse invoquer cette protection, il faut que l'autorité qui a donné son assurance ait été compétente pour le faire, ou que le justiciable ait pu la considérer comme telle (<ref-ruling> consid. 3.6.2 p. 193; <ref-ruling> consid. 3a p. 35 s.). Il faut par ailleurs que l'administré n'ait pas pu se rendre compte immédiatement de l'inexactitude du renseignement obtenu, qu'il se soit fondé sur les assurances dont il se prévaut pour prendre des dispositions auxquelles il ne saurait renoncer sans subir de préjudice et que l'intérêt à une correcte application du droit ne se révèle pas prépondérant sur la protection de la confiance (<ref-ruling> consid. 3.6.2 p. 193; <ref-ruling> consid. 2.5.1 p. 72 s.; <ref-ruling> consid. 6.1 p. 637).
3.2. En l'espèce, la demande d'autorisation de réaliser le garage litigieux avait été régulièrement adressée à la commune, ce qui n'est pas contesté par le canton recourant. Ladite demande était assortie du "plan de situation dressé pour enquête" du 18 septembre 1986 établi par un géomètre breveté ayant qualité de "géomètre officiel". Ce document attestait de la localisation du projet en zone à bâtir ("zone de résidence d'agrément"). Les autorités communales l'ont visé à deux reprises et n'ont pas contesté l'affectation constructible de la partie de la parcelle concernée bien que, conformément à ce qu'a constaté la cour cantonale, elle soit pourtant tenue en vertu de l'art. 104 al. 1 et 2 de la loi cantonale du 4 décembre 1985 sur l'aménagement du territoire et les constructions (LATC; RSV 700.11) de s'assurer que le projet est conforme aux dispositions légales ainsi qu'aux plans d'affectation, et de vérifier si les autorisations cantonales et fédérales préalables nécessaires ont été délivrées. La commune a dès lors transmis le dossier à la centrale cantonale des autorisations de construire, mais non au service cantonal compétent en matière d'autorisation de construire hors zone à bâtir. Puis, à la réception des préavis des services cantonaux consultés, elle a octroyé le permis de construire. Il n'est au demeurant pas allégué que le garage n'aurait pas été conforme au projet mis à l'enquête.
La question de savoir si le constructeur - dont la situation est opposable au propriétaire actuel (<ref-ruling> consid. 2b p. 396; arrêts 1C_482/2017 du 26 février 2018 consid. 2.6.1; 1C_24/2012 du 19 avril 2012 consid. 3 in SJ 2012 I p. 477) - pouvait bénéficier de la protection de la confiance dépend de la question de savoir à qui est imputable l'erreur commise par l'ingénieur géomètre et, cas échéant, par la commune.
La CDAP a considéré que l'erreur du géomètre officiel était imputable à la collectivité publique, ce que soutient également l'intimé, alors que le canton recourant considère qu'elle est imputable au constructeur. Le recourant n'expose toutefois pas le droit cantonal applicable ni n'explique en quoi l'appréciation de la cour cantonale ne pourrait être suivie.
Le géomètre breveté agissait selon la cour cantonale comme géomètre officiel. Le géomètre occupant cette fonction est chargé, en vertu du droit vaudois, d'authentifier la conformité du plan de situation au plan cadastral mis à jour et les indications mentionnées (art. 69 al. 1 ch. 1 i.f. du règlement cantonal du 19 septembre 1986 d'application de la loi du 4 décembre 1985 sur l'aménagement du territoire et les constructions [RLATC; RSV 700.11.1]). Ce plan contient notamment l'affectation réglementaire (art. 69 al. 1 ch. 1 let. d RLATC).
A l'occasion d'un arrêt statuant sur un recours visant un contrôle abstrait des dispositions relatives au rôle du géomètre officiel en matière d'autorisation de construire, le Tribunal fédéral avait considéré que l'exigence légale cantonale de l'art. 69 RLATC de faire authentifier le plan de situation par un ingénieur géomètre breveté était justifiée par le fait que les indications devant être fournies nécessitaient des connaissances et une appréciation juridique qui vont au-delà du simple relevé décrivant la seule situation géographique (arrêt 2P.182/2001 du 18 juin 2002 consid. 2.4.2). Il en allait de même de l'art. 71 RATC, qui prévoit qu'en cas de dérogation aux règlements ou aux plans d'affectation, celle-ci doit être mentionnée sur le plan de situation authentifié par l'ingénieur géomètre breveté. De telles indications ne pouvaient être fournies que moyennant une très bonne connaissance des lois et règlements applicables ainsi que de la jurisprudence y relative ( ibidem). L'intérêt public de l'Etat à ce que les plans soumis à l'enquête en vue d'une construction présentent une forte garantie de fiabilité expliquait qu'il s'en remette, pour l'authentification des plans de situation, aux spécialistes particulièrement qualifiés que sont les ingénieurs géomètres brevetés, "garants de la conformité des plans aux prescriptions légales" ( ibidem consid. 2.4.3 i.f.).
Compte tenu des considérations précitées et en l'absence d'explications complémentaires du canton recourant sur le rôle de l'ingénieur géomètre breveté chargé de l'authentification des plans (<ref-law>), il n'y a pas de raisons de s'écarter de l'appréciation de la CDAP selon laquelle l'erreur de cet intervenant - que la commune n'a pas relevée lors de ses vérifications - ne peut être imputée au constructeur.
En particulier, le recourant ne saurait se fonder sur les observations de l'ARE qui considère que le constructeur ne pouvait se fier au plan d'enquête, trop vague, pour ce qui est de l'affectation du sol et qu'il aurait dès lors manqué à ses obligations. Cette appréciation ne tienten effet compte ni des particularités précitées du droit cantonal vaudois en matière de mise à l'enquête (rôle du géomètre officiel et devoir de vérification de la commune) ni de l'attestation écrite accompagnant le plan d'enquête. Or, comme on l'a vu précédemment, cette attestation indique expressément qu'est concernée la zone de résidence d'agrément, soit la zone à bâtir, dans un contexte, ressortant des constatations non contestées de la cour cantonale, où la parcelle litigieuse est pour une part affectée à la zone constructible et pour une autre part à la zone agricole alors que le plan d'affectation même en vigueur à l'époque, établi en 1987, était particulièrement imprécis s'agissant de la délimitation des zones en raison de l'épaisseur étonnamment inappropriée du trait utilisé. Celui-ci couvre en effet toute la partie ouest de la parcelle litigieuse, en particulier le secteur dans lequel le garage a été effectué dans son intégralité. A supposer qu'avec une diligence allant au-delà de ce que l'on peut attendre du constructeur, celui-ci ait pris, en sus du plan de situation établi ad hoc, connaissance du plan d'affectation en vigueur, on ne saurait lui tenir rigueur de n'avoir pas multiplié les démarches de vérification par une reconstitution historique de la planification alors que le géomètre officiel et la commune considéraient que le projet de garage était situé en zone à bâtir. En l'absence d'éléments au dossier démontrant que le constructeur devait connaître la situation particulière de sa parcelle - par exemple des lettres ou procès-verbaux démontrant l'existence de pourparlers avec les autorités ayant trait spécifiquement à la délimitation initiale entre zone constructible et non constructible de ladite parcelle -, celui-ci n'a pas à subir les conséquences de l'erreur commise par le géomètre officiel, non remise en cause par la commune, et conforme à l'imprécision du plan d'affectation en vigueur lors de la demande d'autorisation de construire.
En définitive, dans ces circonstances très particulières, le constructeur doit pouvoir bénéficier du principe de la bonne foi en vertu de la confiance légitime qu'il a placée en l'espèce dans le comportement de l'administration.
4.
Enfin, le canton recourant, qui déplore une violation de l'égalité de traitement, exprime sa volonté d'obtenir une jurisprudence de principe "dont il résulterait que l'administré auquel il est reproché et établi qu'il a violé, de mauvaise foi, le droit dérogatoire dans le domaine des constructions hors des zones à bâtir" ne puisse prétendre en tirer avantage. Or, ainsi qu'on l'a vu, on ne saurait retenir, dans les circonstances très particulières de la présente cause, une mauvaise foi du constructeur: s'agissant d'une erreur qui est imputable à la collectivité publique et portant précisément sur l'affectation en zone constructible du terrain, on ne peut, contrairement à ce qu'allègue le canton recourant, reprocher au constructeur - ou à l'ingénieur mandaté pour le projet - de ne pas s'être "renseign[é] également auprès de l'autorité cantonale compétente". Cela étant, une abondante jurisprudence consacre une pratique stricte en matière d'ordres de remise en état pour des constructions ou installations érigées en violation du principe de la séparation des territoires bâtis et non bâtis sur laquelle la cour de céans n'entend pas revenir (cf. par exemple, l'arrêt récent 1C_508/2018 du 15 juillet 2019). La présente affaire, au caractère extraordinaire, ne remet en rien en cause cette pratique ni, par conséquent, ne consacre une violation du principe de l'égalité de traitement.
Aussi l'appréciation des premiers juges selon laquelle, en dépit de sa non-conformité aux règles légales, le garage litigieux peut être maintenu n'est-elle pas en contradiction avec la jurisprudence fédérale en matière de renonciation exceptionnelle à la remise en état des lieux.
5.
Il résulte de ce qui précède que le recours doit être rejeté. Le présent arrêt sera rendu sans frais (<ref-law>). En revanche, l'intimé, représenté par un avocat, a droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Une indemnité de dépens de 2'000 fr. est accordée à l'intimé, à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties, à la Municipalité de Montreux, au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, et à l'Office fédéral du développement territorial.
Lausanne, le 22 juillet 2019
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Chaix
La Greffière : Sidi-Ali