Faits: A. Né en 1964 au Tessin, X._ a hérité la seule nationalité italienne de son père, nonobstant l'origine suisse de sa mère. Il a passé sa prime enfance dans ce canton jusqu'à ce que ses parents ne décident d'aller s'établir en Italie, non loin de la frontière suisse, à B._ où il a commencé sa scolarité obligatoire qu'il a ensuite poursuivie, après le décès de son père, à Bergame, avant d'entreprendre une formation d'électricien dans la région de Côme. En 1985, à l'âge de dix-neuf ans, X._ s'est marié avec une ressortissante italienne établie au Tessin. Il est venu la rejoindre au bénéfice d'une autorisation de séjour délivrée au titre du regroupement familial. Il semble qu'il ait alors occupé différents postes dans des entreprises sises en Italie et en Suisse, comme opérateur programmeur. Après avoir divorcé de son épouse, en 1991, il a décidé, étant titulaire d'un permis d'établissement, de rester au Tessin où il a exercé successivement diverses activités (chauffeur routier, vendeur, «placeur» de filles de cabarets pour une agence active dans toute la Suisse). A cette époque, il a été condamné à deux reprises, la première fois à cinq jours d'emprisonnement avec sursis pendant deux ans pour faux dans les titres (le 28 janvier 1992) et, la seconde fois, à quinze jours d'emprisonnement avec sursis pendant deux ans et 1'200 fr. d'amende pour infraction aux règles de la circulation routière (le 5 mars 1993). Après s'être remarié avec une ressortissante brésilienne en mai 1994, il a encore été condamné, le 30 juin suivant, à cinq jours d'arrêts pour avoir fait entrer illégalement en Suisse deux clandestins péruviens. Au mois de novembre de la même année, une nouvelle instruction pénale a été ouverte contre lui pour diverses infractions à la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 142.20); il lui était reproché d'avoir fait transiter ou entrer illégalement en Suisse, entre l'automne 1993 et le mois de novembre 1994, un grand nombre de travailleurs clandestins. En décembre 1994, il est parti quelque temps au Brésil avec sa femme. A son retour, l'autorité compétente tessinoise a constaté que son permis d'établissement avait pris fin le 19 mai 1995, en raison d'un séjour à l'étranger d'une durée supérieure à six mois (cf. décision du Conseil d'Etat tessinois du 17 avril 1996 confirmée, sur recours, le 19 mars 1997 par le Tribunal fédéral). B. Le 1er avril 1997, bien que dépourvu de titre de séjour, X._ est venu s'installer avec son épouse à Lausanne, dans un appartement qu'il a transformé en salon de massage où trois ou quatre femmes ont constamment travaillé jusqu'à la fin de l'année 1999, y compris, durant les premiers temps, sa propre épouse, dont il a divorcé en 1998. Pendant cette période (1997 à 1998), il a été condamné à trois reprises, la première fois par contumace le 20 août 1997 par le Tribunal correctionnel de Mendrisio à une peine de six mois d'emprisonnement avec sursis pendant deux ans pour infractions répétées et, en partie graves, à la loi fédérale sur le séjour et l'établissement des étrangers et, les deux autres fois, à des peines respectivement de sept jours d'emprisonnement et 1'000 francs d'amende (le 30 octobre 1997) et vingt jours d'arrêt et 1'000 fr. d'amende (le 9 juin 1999) pour violation des règles de la circulation routière. Dès l'année 2000, X._ s'est ensuite occupé, en association avec une nouvelle compagne, également d'origine brésilienne, d'un autre salon de massage loué par cette dernière; plus spacieux, cet établissement a abrité en permanence au moins six prostituées jusqu'à sa fermeture, le 17 juillet 2000, après que X._ eut été interpellé par la police et inculpé, ainsi que sa compagne, d'encouragement à la prostitution et d'infraction à loi fédérale sur le séjour et l'établissement des étrangers. Frappé d'une interdiction d'entrée en Suisse valable jusqu'au 27 juillet 2003, il est reparti au Brésil le 11 août 2000 en compagnie de son amie. Un mois plus tard, il est rentré en Europe où il a vécu apparemment en Italie pendant une période de quatre ou cinq mois entrecoupée de brefs séjours en Suisse. En novembre 2001, il a été une nouvelle fois arrêté par la police pour avoir fait entrer de manière illégale, dès le mois de janvier de cette même année, des prostituées brésiliennes pour le compte d'une tierce personne exploitant un bar à D._; parmi celles-ci, au moins deux ont travaillé pour son compte personnel, en ce sens qu'il s'est chargé de les loger dans un studio qu'il avait loué et de les mettre en relation avec des clients au moyen de petites annonces publiées dans la presse. Par jugement du 30 avril 2002, le Tribunal correctionnel d'arrondissement de Lausanne a condamné X._ pour encouragement à la prostitution et infraction à la loi fédérale sur le séjour et l'établissement des étrangers à une peine de 10 mois d'emprisonnement, sous déduction de 115 jours de détention préventive, ainsi qu'à une amende de 5'000 fr. Partiellement complémentaire à trois de ses condamnations antérieures, cette peine a été assortie de la révocation du sursis de deux ans accordé en août 1997 par le Tribunal correctionnel de Mendrisio, ainsi que d'une expulsion du territoire suisse pour une durée de cinq ans. Incarcéré dès le 8 mai 2002, X._ a bénéficié d'une libération conditionnelle le 21 novembre suivant; en revanche, la Commission de libération n'a pas consenti à différer son expulsion à titre d'essai (décision du 13 novembre 2002). Aux policiers chargés d'assurer son refoulement qui l'ont pris en charge, il a déclaré, le jour de sa sortie de prison, vouloir quitter la Suisse pour la France «dans la journée» après avoir rencontré son avocat, tout en refusant de signer l'accusé de réception d'une nouvelle décision d'interdiction d'entrée en Suisse valable jusqu'au 27 juillet 2008. En réalité, il n'est pas parti. Par la suite, il a obtenu que son expulsion soit différée à titre d'essai (arrêt du 20 janvier 2003 de la Cour de cassation pénale du Tribunal cantonal vaudois). C. Le 28 janvier 2003, X._ a déposé une demande de permis de séjour avec activité lucrative qui a été écartée par le Service cantonal de la population, pour des motifs tirés de l'ordre et de la sécurité publics (décision du 18 mars 2003). Saisi d'un recours contre cette décision, le Tribunal administratif du canton de Vaud (ci-après: le Tribunal administratif) l'a rejeté, par arrêt du 24 novembre 2003, pour les mêmes raisons que le Service cantonal de la population, après avoir néanmoins autorisé l'intéressé à exercer une activité lucrative pendant la durée de la procédure cantonale. Depuis le 1er septembre 2003, ce dernier a repris, en association avec un ami, l'exploitation d'un hôtel-restaurant à Lausanne. D. Agissant par la voie du recours de droit administratif, X._ demande au Tribunal fédéral d'annuler l'arrêt précité du Tribunal administratif et de lui «renouveler» son autorisation de séjour ou, subsidiairement, de renvoyer le dossier au Service de la population pour nouvelle décision. A titre préalable, il requiert le bénéfice de l'effet suspensif. Le Service de la population s'en remet aux déterminations du Tribunal administratif, lequel conclut au rejet du recours, à l'instar de l'Office fédéral de l'immigration, de l'intégration et de l'émigration. Autant que de besoin, les moyens des parties seront repris ci-après. E. Le 13 mai 2004, le Service de la population a fait parvenir au Tribunal fédéral une photocopie d'un procès-verbal d'audition établi le 27 avril 2004 par la Police cantonale vaudoise dans le cadre d'une procédure pénale ouverte contre X._ pour recel.