Faits:
Faits:
A. A._, ressortissant du Kosovo, né le 6 mars 1967, a présenté une demande de prestations de l'assurance-invalidité le 7 décembre 1998, en invoquant des «problèmes psychiques et (de) dos».
Dans un rapport du 25 janvier 1999, le docteur D._ a diagnostiqué des cervicobrachialgies et des lombosacralgies chroniques, des troubles de l'adaptation avec réaction dépressive prolongée, ainsi qu'une personnalité de type borderline. Par ailleurs, outre deux courtes périodes d'interruption de travail entre le 6 juillet 1996 et le 6 juillet 1997, il a attesté une incapacité de travail entière depuis le 30 septembre 1997. Devant l'impossibilité d'objectiver les plaintes de l'assuré au plan somatique, le docteur D._ a adressé celui-ci au Département de psychiatrie D._ où les médecins ont posé le diagnostic d'épisode dépressif moyen sans syndrome somatique (F32.10), trouble somatoforme douloureux persistant (F450) et difficultés liées à l'emploi et au chômage (Z56) ainsi que dans les rapports avec le conjoint (Z630). Sur la base de ces constatations, ils ont attesté une incapacité de travail entière à partir du 15 juillet 1998, et ce pour une durée indéterminée (rapport du 30 avril 1999 établi par les doctoresses R._ et W._, respectivement chef de clinique et médecin-assistant au Département de psychiatrie D._).
Par décision du 20 août 1999, l'Office AI pour le canton de Vaud (ci-après : l'office AI) a refusé toute prestation à l'assuré, en considérant que celui-ci ne présentait pas d'atteinte à la santé invalidante au sens de la loi.
Par décision du 20 août 1999, l'Office AI pour le canton de Vaud (ci-après : l'office AI) a refusé toute prestation à l'assuré, en considérant que celui-ci ne présentait pas d'atteinte à la santé invalidante au sens de la loi.
B. A._ a recouru contre cette décision en concluant au bénéfice de mesures de réadaptation professionnelle ou à l'octroi d'une rente d'invalidité.
L'office AI a conclu au rejet du recours en faisant valoir, outre les motifs déjà exposés dans sa décision du 20 août 1999, que A._ ne remplissait pas la condition d'assurance, car il n'était plus au bénéfice d'une autorisation de séjour et avait définitivement quitté la Suisse le 31 janvier 1997, selon une attestation du 28 janvier 1999 émanant de l'Office cantonal de contrôle des habitants et de police des étrangers (ci-après : la police des étrangers).
Par jugement du 27 mars 2000, le Tribunal des assurances du canton de Vaud a admis le recours formé par A._ et annulé la décision attaquée, en renvoyant le dossier à l'office AI pour instruction complémentaire et nouvelle décision au sens des considérants.
Par jugement du 27 mars 2000, le Tribunal des assurances du canton de Vaud a admis le recours formé par A._ et annulé la décision attaquée, en renvoyant le dossier à l'office AI pour instruction complémentaire et nouvelle décision au sens des considérants.
C. L'office AI interjette recours de droit administratif contre ce jugement dont il requiert l'annulation, en reprenant les arguments et les conclusions présentés en instance cantonale.
A._ conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales préavise en faveur de son admission.

Considérant en droit:
Considérant en droit:
1. La loi fédérale sur la partie générale du droit des assurances sociales (LPGA) du 6 octobre 2000, entrée en vigueur le 1er janvier 2003, et les modifications qu'elle a notamment entraînées dans le domaine de l'assurance-invalidité, ne sont pas applicables au présent litige, dès lors que le juge des assurances sociales n'a pas à prendre en considération les modifications du droit ou de l'état de fait postérieures à la date déterminante de la décision litigieuse du 20 août 1999 (<ref-ruling> consid. 1, 121 V 366 consid. 1b). Il en va de même des dispositions de la novelle du 21 mars 2003 modifiant la LAI (4ème révision), entrée en vigueur le 1er janvier 2004 (RO 2003 3852).
1. La loi fédérale sur la partie générale du droit des assurances sociales (LPGA) du 6 octobre 2000, entrée en vigueur le 1er janvier 2003, et les modifications qu'elle a notamment entraînées dans le domaine de l'assurance-invalidité, ne sont pas applicables au présent litige, dès lors que le juge des assurances sociales n'a pas à prendre en considération les modifications du droit ou de l'état de fait postérieures à la date déterminante de la décision litigieuse du 20 août 1999 (<ref-ruling> consid. 1, 121 V 366 consid. 1b). Il en va de même des dispositions de la novelle du 21 mars 2003 modifiant la LAI (4ème révision), entrée en vigueur le 1er janvier 2004 (RO 2003 3852).
2. Dans un premier moyen, l'office AI soutient que l'intimé n'est plus domicilié en Suisse depuis le 31 janvier 1997, si bien que, devenu invalide postérieurement à cette date, il ne réalise pas la condition d'assurance.
2.1 Aux termes de l'<ref-law>, dans sa teneur en vigueur - déterminante en l'espèce - jusqu'au 31 décembre 2000, les ressortissants suisses et les étrangers n'avaient droit aux prestations de l'assurance-invalidité que s'ils étaient assurés lors de la survenance de l'invalidité. Sont notamment assurées à l'assurance-invalidité les personnes physiques domiciliées en Suisse (<ref-law> en relation avec l'<ref-law>). Pour la définition du domicile, le domicile au sens du code civil (CC) est déterminant (<ref-law>).
Selon l'<ref-law>, le domicile de toute personne est au lieu où elle réside avec l'intention de s'y établir. La notion de domicile comporte, d'après la jurisprudence, deux éléments : la résidence dans un lieu donné (critère objectif) et l'intention d'y demeurer (critère subjectif). Pour savoir si une personne réside dans un lieu avec l'intention de s'y établir, ce n'est pas la volonté interne de l'intéressé qui est déterminante, mais les circonstances objectives, reconnaissables pour les tiers, qui permettent de déduire une telle intention (<ref-ruling> consid. 2a; <ref-ruling> consid. 2b, 169 consid. 2b). En règle ordinaire, les travailleurs étrangers qui exercent une activité rémunérée en Suisse sur la base d'une autorisation de séjour saisonnière ne peuvent pas, selon la jurisprudence, se créer un domicile au sens de l'<ref-law>. L'intention de s'établir en Suisse ne saurait en effet être prise en compte, en principe, tant que le droit public empêche à long terme sa concrétisation (<ref-ruling> consid. 2). A l'inverse, on doit admettre que les travailleurs étrangers au bénéfice d'une autorisation de séjour à l'année peuvent, s'ils en ont l'intention et que celle-ci est reconnaissable, élire domicile en Suisse (cf. <ref-ruling> consid. 2b; Jacques-Michel Grossen, Les personnes physiques, in : Traité de droit civil suisse, tome II/2, éd. française de Schweizerisches Privatrecht, p. 71).
2.2 En l'espèce, selon l'attestation établie le 28 janvier 1999 par la police des étrangers, le recourant est «parti à l'étranger le 31 janvier 1997» après avoir résidé sans interruption en Suisse depuis le 5 mars 1993. Il était en outre, toujours selon cette attestation, au bénéfice d'un permis «B» valable jusqu'au 4 mars 1996. Dans sa demande de prestations du 7 décembre 1998, le recourant a, par ailleurs, indiqué avoir travaillé du 3 janvier 1994 au 1er septembre 1997 au service de M._ Sàrl. L'existence de cette activité est confirmée par un extrait du compte individuel de l'assuré qui atteste également le paiement régulier de cotisations depuis le mois d'avril 1990.
Au vu de ces circonstances, singulièrement du fait que l'intimé a résidé et travaillé durant plusieurs années au bénéfice d'une autorisation de séjour à l'année (permis «B»), on doit admettre que, bien avant le dépôt de sa demande de prestations le 7 décembre 1998, il s'était créé un domicile en Suisse. Par ailleurs, contrairement aux indications fournies par la police des étrangers, il est resté dans le canton de Vaud après le 31 janvier 1997, comme en témoignent les pièces médicales au dossier (cf. rapport du 25 janvier 1999 du docteur D._ et rapport du 30 avril 1999 des doctoresses R._ et W._). Il y réside d'ailleurs encore à ce jour, à Villeneuve, si l'on en croit les indications mentionnées sur le mémoire de réponse qu'il a adressé au tribunal.
Force est ainsi de constater que l'intimé a maintenu un domicile en Suisse, nonobstant le retrait de son permis de séjour (voir pour comp. dans le domaine de l'assurance-maladie <ref-ruling> consid. 5.2 et la référence). Une telle mesure ne conduit en effet pas nécessairement et automatiquement, contrairement à ce que voudrait le recourant, à la perte du domicile en Suisse, ce résultat n'intervenant que lorsque l'étranger abandonne, de manière reconnaissable pour les tiers, l'intention de s'y établir (cf. Andreas Bucher, Personnes physiques et protection de la personnalité, 4ème éd., Bâle 1999, p. 87 no 365; Eugen Bucher, Berner Kommentar zum schweizerischen Privatrecht, note 26 ad <ref-law>). Or, en l'occurrence, l'intimé a clairement manifesté la volonté contraire, puisqu'il s'est opposé au non-renouvellement de son autorisation de séjour et qu'il a conservé - illégalement semble-t-il - sa résidence dans le canton de Vaud.
2.3 Vu son domicile en Suisse lors de la survenance de son invalidité, l'intimé était donc obligatoirement assuré à l'AI (<ref-law> en relation avec l'<ref-law>), si bien qu'il réalise la condition d'assurance prévue à l'art. 6 al. 1 aLAI (cf. aussi <ref-ruling> consid. 5).
2.3 Vu son domicile en Suisse lors de la survenance de son invalidité, l'intimé était donc obligatoirement assuré à l'AI (<ref-law> en relation avec l'<ref-law>), si bien qu'il réalise la condition d'assurance prévue à l'art. 6 al. 1 aLAI (cf. aussi <ref-ruling> consid. 5).
3. L'office AI fait également valoir, en se fondant sur les constatations du docteur D._, que l'intimé peut parfaitement travailler dans une activité adaptée, à condition de ménager son dos. En outre, il nie toute invalidité en raison de troubles d'ordre psychique.
Cette opinion est dénuée de fondement. Certes, le docteur D._ a-t-il relevé que, d'un point de vue somatique, l'état de santé de l'intimé était certainement compatible avec l'exercice d'une activité légère. Ce médecin n'en a pas moins mis en évidence des troubles d'ordre psychique (notamment une dépression prolongée associée à une personnalité de type bordeline) et attesté une incapacité de travail entière depuis le 30 septembre 1997, ce que ses confrères du Département de psychiatrie D._ ont, pour l'essentiel, confirmé, complétant même le diagnostic par la mention d'un trouble somatoforme douloureux persistant. Du moment que ces constatations médicales - et les conclusions que les médecins en ont tirées - ne sont contredites par aucune autre pièce au dossier, l'office AI ne pouvait, comme il l'a fait, s'en écarter purement et simplement. S'il nourrissait des doutes sur leur bien-fondé, il devait au contraire, comme l'ont à juste raison rappelé les premiers juges, ordonner des mesures d'instruction complémentaires. Le renvoi de la cause à l'administration pour qu'elle reprenne l'instruction du cas - également sous l'angle économique - et rende une nouvelle décision, est donc justifié.
Cette opinion est dénuée de fondement. Certes, le docteur D._ a-t-il relevé que, d'un point de vue somatique, l'état de santé de l'intimé était certainement compatible avec l'exercice d'une activité légère. Ce médecin n'en a pas moins mis en évidence des troubles d'ordre psychique (notamment une dépression prolongée associée à une personnalité de type bordeline) et attesté une incapacité de travail entière depuis le 30 septembre 1997, ce que ses confrères du Département de psychiatrie D._ ont, pour l'essentiel, confirmé, complétant même le diagnostic par la mention d'un trouble somatoforme douloureux persistant. Du moment que ces constatations médicales - et les conclusions que les médecins en ont tirées - ne sont contredites par aucune autre pièce au dossier, l'office AI ne pouvait, comme il l'a fait, s'en écarter purement et simplement. S'il nourrissait des doutes sur leur bien-fondé, il devait au contraire, comme l'ont à juste raison rappelé les premiers juges, ordonner des mesures d'instruction complémentaires. Le renvoi de la cause à l'administration pour qu'elle reprenne l'instruction du cas - également sous l'angle économique - et rende une nouvelle décision, est donc justifié.
4. L'intimé, qui obtient gain de cause, a droit à une indemnité de dépens à la charge du recourant qui succombe (art. 159 al. 1 OJ).

Par ces motifs, le Tribunal fédéral des assurances prononce:
Par ces motifs, le Tribunal fédéral des assurances prononce:
1. Le recours est rejeté.
1. Le recours est rejeté.
2. Il n'est pas perçu de frais de justice.
2. Il n'est pas perçu de frais de justice.
3. L'office recourant versera à l'intimé la somme de 2'500 fr. (y compris la taxe à la valeur ajoutée) à titre de dépens pour la procédure fédérale.
3. L'office recourant versera à l'intimé la somme de 2'500 fr. (y compris la taxe à la valeur ajoutée) à titre de dépens pour la procédure fédérale.
4. Le présent arrêt sera communiqué aux parties, au Tribunal des assurances du canton de Vaud et à l'Office fédéral des assurances sociales.
Lucerne, le 30 septembre 2004
Au nom du Tribunal fédéral des assurances
Le Président de la Ire Chambre: p. la Greffière: