Faits: A. A.a Dès janvier 1976, A._ a travaillé pour la Banque X._ (ci-après : X._), une société de droit anglais qui possède plusieurs succursales en Suisse, dont une à Genève. Après avoir commencé son activité en qualité de simple employé, A._ a bénéficié régulièrement de promotions et, en 1999, il a été nommé directeur général adjoint, responsable de la gestion, de la supervision et du contrôle de tout le service administratif de la succursale genevoise, dont il était le numéro 2. Les rapports de performance de A._ ont toujours été élogieux. Aucun élément ne démontre que celui-ci aurait fait l'objet, avant son licenciement, d'un quelconque reproche de son employeur au cours de plus de 26 années de service. A la fin de l'année 2000, l'avenir de la banque était incertain et de nombreux employés, dont A._, ont sollicité un certificat de travail intermédiaire. Le 31 décembre 2000, A._ a obtenu un certificat très positif du directeur général. Dès le 1er janvier 2002, le salaire annuel brut de A._ a été porté à 357'012 fr. Un bonus de 112'000 fr. lui a également été versé avec son salaire d'avril 2002, en reconnaissance de sa performance réalisée durant l'exercice 2001. A.b La réglementation interne de X._ en cas de licenciement pour des motifs autres que des manquements à des obligations professionnelles ou disciplinaires, des départs volontaires ou à la retraite à l'âge normal prévoyait le versement d'une indemnité de licenciement équivalant à deux semaines de salaire de base par année de service. Pour les employés dont l'âge se situait entre 45 et 56 ans, une indemnité supplémentaire venait s'y ajouter. A l'âge de 52 ans, un employé licencié avait ainsi droit à un montant supplémentaire s'élevant à 60 % de l'indemnité de licenciement. X._ a aussi édicté un manuel du personnel mentionnant des règles de conduite et la sanction assortissant leur violation. Ce document stipulait entre autres que, dans les cas graves, notamment la mauvaise conduite, des mesures disciplinaires allant jusqu'au licenciement immédiat pouvaient être prises. Le point 5.3 définissait la mauvaise conduite ("misconduct" dans la version originale) comme toute infraction au règlement de la banque ou autre conduite offensante envers un client ou un collaborateur de la banque. Après le paragraphe décrivant les conséquences de l'avertissement, il était indiqué : "Les cas graves feront l'objet d'une décision de suspension ou de renvoi immédiat incombant au Directeur des Ressources Humaines après consultation du Directeur d'agence/secteur." Selon la responsable des ressources humaines, le terme de "misconduct" devait être traduit par inadéquation ou insuffisance de la prestation eu égard aux responsabilités du poste. A.c B._, qui a passé 33 ans au sein de X._ à Genève, a assumé, dès 1992, la responsabilité du service des immeubles et de l'équipement. Son supérieur direct était C._, lui-même sous les ordres de A._. Il s'est avéré que B._ a commis pendant au moins dix ans des actes illicites consistant à se présenter comme un gestionnaire de la banque en charge de clients spéciaux, en utilisant diverses techniques pour offrir à ses victimes l'accès à des opérations fictives comportant des rendements extrêmement élevés. Au total, 29 personnes ont été lésées pour un montant dépassant les 11 millions de francs. B._ a été condamné à 5 ans de réclusion à raison de ces actes. Il a été retenu que ni C._, ni l'employée qui occupait le bureau contigu à celui de B._ n'ont eu le moindre soupçon concernant les activités illicites exercées par ce dernier jusqu'en décembre 2001. A la fin de l'année 2001, certains responsables de la banque ont eu des soupçons concernant les activités illicites de B._, mais ils n'en ont informé ni A._ ni C._. Le 15 janvier 2002, A._ a été mis au courant des agissements de B._. Il a aussitôt mis sur pied une réunion pour le lendemain, afin de recueillir les informations détenues par chacun et de prendre les décisions s'imposant. Le directeur général, absent à ce moment, a déclaré à son retour que les mesures appropriées avaient été prises. L'enquête interne menée par la banque n'a signalé aucune faute relevant de la compétence de A._, alors qu'elle s'est révélée plus critique envers C._. A.d Le 29 avril 2002, A._ a été licencié avec effet au 31 juillet 2002. La lettre de licenciement indiquait que "suite aux graves événements qui se sont produits au début de cette année au sein de notre établissement, à la suite d'actions commises par l'un de nos anciens collaborateurs dont vous assumiez la responsabilité, nous devons constater que le lien de confiance qui vous liait à notre banque n'existe plus". Cette lettre ne comportait aucune référence à une violation précise des règles de la banque. Il a été retenu que A._ avait été licencié en raison de sa position hiérarchique supérieure, afin de sauver l'image de X._ ternie par l'affaire B._, alors que les reproches allégués contre le directeur général adjoint n'ont pu être établis. Ce dernier avait ainsi tenu le rôle du "fusible". Au moment de son licenciement, A._ avait accompli 26 ans et 7 mois au service de X._ et était âgé de 52 ans. C._ a été licencié en même temps que A._ et pour les mêmes motifs. Il a négocié et obtenu une indemnité de départ de 300'000 fr. à raison des longs rapports de service, X._ affirmant avoir fait un geste lié à la situation personnelle de cet employé. Le 27 mai 2002, A._ s'est opposé par écrit à son licenciement, réclamant le versement des indemnités contractuelles prévues. X._ a répondu qu'un licenciement sans indemnité était justifié, car A._ avait failli à son devoir de surveillance. B. Le 4 novembre 2002, A._ a déposé une demande auprès de la Juridiction des prud'hommes du canton de Genève, concluant au paiement par X._ d'une indemnité de licenciement de 583'943,50 fr. sur la base des directives internes de la banque et de 178'500 fr. pour résiliation abusive du contrat de travail. Il a par la suite amplifié sa demande de 100'000 fr. à titre d'indemnité pour tort moral. Par jugement du 3 novembre 2003, le Tribunal des prud'hommes a condamné X._ à payer à A._ 584'016,70 fr. brut à titre d'indemnité de départ et 29'750 fr. net correspondant à un mois de salaire à titre d'indemnité pour résiliation abusive, les deux montants portant intérêt à 5 % l'an dès le 1er août 2002. Les prétentions de A._ en tort moral ont été rejetées. Statuant sur appel de X._ et appel incident de A._, la Cour d'appel de la juridiction des prud'hommes, par arrêt du 9 février 2005, a confirmé le jugement de première instance. C. Contre l'arrêt du 9 février 2005, X._ (la défenderesse) interjette un recours en réforme au Tribunal fédéral. Elle conclut à l'admission du recours et à la réforme de l'arrêt du 9 février 2005 dans le sens de l'annulation du jugement rendu par le Tribunal des prud'hommes le 3 novembre 2003 et du déboutement de A._ de toutes ses conclusions. A._ (le demandeur) conclut à l'irrecevabilité du recours, subsidiairement à son rejet et à la confirmation de l'arrêt entrepris.