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.

Le Tribunal fédéral considère en droit:
1. 1.1 Interjeté par la défenderesse, qui a succombé dans ses conclusions libératoires, et dirigé contre un jugement final rendu en dernière instance cantonale par un tribunal supérieur (art. 48 al. 1 OJ), le recours porte sur une contestation civile (cf. <ref-ruling> consid. 2.1) dont la valeur litigieuse dépasse largement le seuil de 8'000 fr. (art. 46 OJ). Il est en principe recevable, puisqu'il a été déposé en temps utile (art. 32 al. 2 et 54 al. 1 OJ) et dans les formes requises (art. 55 OJ).
1.2 La défenderesse est une société anglaise qui dispose d'une succursale en Suisse. C'est donc à juste titre que la cour cantonale a admis la compétence des tribunaux suisses, en se référant à l'art. 5 de la Convention du 16 septembre 1988 concernant la compétence judiciaire et l'exécution des décisions en matière civile et commerciale (Convention de Lugano; RS 0.275.11). Il n'est par ailleurs pas contesté que le droit suisse est applicable aux relations contractuelles entre les parties (<ref-law>).
2. Saisi d'un recours en réforme, le Tribunal fédéral doit conduire son raisonnement juridique sur la base des faits contenus dans la décision attaquée, à moins que des dispositions fédérales en matière de preuve n'aient été violées, qu'il y ait lieu de rectifier des constatations reposant sur une inadvertance manifeste (art. 63 al. 2 OJ) ou qu'il faille compléter les constatations de l'autorité cantonale, parce que celle-ci n'a pas tenu compte de faits pertinents, régulièrement allégués et clairement établis (art. 64 OJ; <ref-ruling> consid. 2.2, 136 consid. 1.4 p. 140). Hormis ces exceptions que le recourant doit invoquer expressément, il ne peut être présenté de griefs contre les constatations de fait, ni de faits ou de moyens de preuve nouveaux (art. 55 al. 1 let. c OJ).
En l'espèce, la défenderesse commence par présenter de nombreux faits ne ressortant pas de l'arrêt attaqué, en alléguant que la cour cantonale aurait commis des inadvertances manifestes, ainsi que des violations de règles fondamentales de procédure liées à l'appréciation des preuves. Un tel procédé n'est pas admissible. En effet, la recourante n'indique nullement en quoi consisteraient les inadvertances ou les violations des règles de procédure dont elle se prévaut. Elle se contente de compléter les constatations cantonales en présentant sa propre version des événements. Or, un recours en réforme n'est pas un appel et ne permet en aucun cas de remettre en cause l'appréciation des preuves et les constatations de fait qui en découlent (<ref-ruling> consid. 6.5 et les arrêts cités).
Dans la mesure où la défenderesse se fonde sur des faits ne ressortant pas de l'arrêt entrepris et remet en cause, sous le couvert de l'art. 63 al. 2 OJ, l'appréciation des preuves, elle formule des critiques qui ne sont pas admissibles. La Cour de céans examinera donc les griefs soulevés en regard des seuls faits ressortant de la décision attaquée.
3. La défenderesse s'en prend à l'interprétation du contrat à laquelle s'est livrée la cour cantonale pour reconnaître le droit du demandeur à une indemnité de départ. Elle lui reproche d'une part de ne pas avoir retenu que cette indemnisation était réservée aux licenciements économiques et, d'autre part, de ne pas avoir admis que le licenciement était fondé sur un cas de mauvaise conduite.
3.1 En présence d'un litige sur l'interprétation de clauses contractuelles, le juge doit tout d'abord s'efforcer de déterminer la commune et réelle intention des parties, sans s'arrêter aux expressions ou dénominations inexactes dont elles ont pu se servir, soit par erreur, soit pour déguiser la nature véritable de la convention (<ref-law>). Si la volonté réelle des parties ne peut pas être établie ou si elle est divergente, le juge doit interpréter les comportements et les déclarations selon la théorie de la confiance (<ref-ruling> consid. 3.1; <ref-ruling> consid. 2.2 p. 422). Il doit donc rechercher comment une déclaration ou une attitude pouvait être comprise de bonne foi en fonction de l'ensemble des circonstances (<ref-ruling> consid. 2.2; <ref-ruling> consid. 3.2; <ref-ruling> consid. 2.5). L'application du principe de la confiance est une question de droit que le Tribunal fédéral, saisi d'un recours en réforme, peut examiner librement. Pour trancher cette question de droit, il faut cependant se fonder sur le contenu de la manifestation de volonté et sur les circonstances, lesquelles relèvent du fait (ATF <ref-ruling> consid. 3.2 p. 425 et les arrêts cités).
La cour cantonale a examiné, sous l'angle du principe de la confiance, les règlements internes de la banque pour se prononcer sur le droit du demandeur à obtenir une indemnité de départ. Elle s'est en premier lieu fondée sur le texte des documents remis aux employés, sans tenir compte des intentions éventuellement divergentes de leur auteur. Elle a considéré qu'il ressortait sans ambiguïté du texte communiqué aux employés que la politique mettant en place des indemnités en cas de licenciement s'appliquait à toute résiliation du contrat de travail qui n'était pas motivée par des manquements à des obligations professionnelles ou disciplinaires et ne se limitait pas aux seuls licenciements économiques. Contrairement à ce que soutient la défenderesse, on ne voit manifestement pas que l'on puisse reprocher à la cour cantonale une violation de l'<ref-law> pour ne pas avoir interprété ces règles comme limitant les indemnités de départ aux seuls licenciements économiques. En effet, les documents remis aux employés n'indiquaient pas ce cas de figure et l'arrêt attaqué retient qu'il n'était pas établi qu'une telle restriction ait été portée à la connaissance du demandeur, la cour cantonale doutant même qu'elle corresponde à la volonté de l'employeur.
3.2 Quant au point de savoir si l'indemnité de départ aurait dû être refusée au demandeur en raison de sa "mauvaise conduite", la critique ne relève pas de l'interprétation du règlement interne de la banque, dès lors qu'il n'est pas contesté que, dans un tel cas, les indemnités de départ ne sont pas dues. La banque s'en prend en définitive aux motifs du congé, puisqu'elle reproche aux juges de ne pas avoir admis que la résiliation découlait des manquements du demandeur constitutifs de "mauvaise conduite".
La défenderesse perd de vue que les motifs du licenciement relèvent du fait et, par voie de conséquence, lient le Tribunal fédéral saisi d'un recours en réforme (<ref-ruling> consid. 4.1 p. 702; <ref-ruling> consid. 2a). Lorsqu'elle cherche à démontrer que le demandeur a violé les règlements internes de la banque et que c'est en raison de sa mauvaise conduite qu'il a été licencié, elle formule donc des critiques qui ne sont pas admissibles.
Au demeurant, selon l'arrêt attaqué, la défenderesse n'est parvenue à démontrer aucun manquement professionnel de la part du demandeur. Dans ces circonstances, on ne peut faire grief à la cour cantonale d'avoir appliqué les règlements contrairement à leur sens, en allouant au demandeur l'indemnité de départ prévue par ceux-ci.
4. En dernier lieu, la défenderesse reproche à la cour cantonale d'avoir violé le droit fédéral, en particulier l'art. 336 al. 1 let. c CO, en considérant qu'elle avait mis fin au contrat de travail du demandeur de manière abusive.
4.1 Selon le principe posé à l'<ref-law>, le contrat de travail conclu pour une durée indéterminée peut être résilié par chacune des parties. En droit suisse du travail prévaut la liberté de la résiliation, de sorte que, pour être valable, un congé n'a en principe pas besoin de reposer sur un motif particulier (arrêt du Tribunal fédéral 4C.174/2004 du 5 août 2004, consid. 2.1; cf. ATF <ref-ruling> consid. 2a). Le droit fondamental de chaque cocontractant de mettre unilatéralement fin au contrat est cependant limité par les dispositions sur le congé abusif (<ref-law>; <ref-ruling> consid. 4.1), notamment par l'art. 336 al. 1 let. c CO qui qualifie d'abusif le congé donné par une partie seulement afin d'empêcher la naissance de prétentions juridiques de l'autre partie résultant du contrat de travail.
Bien que l'arrêt attaqué ne soit pas très clair à ce sujet, il semble que les juges aient, à juste titre, écarté l'application de cette dernière disposition. En effet, il a été retenu que la défenderesse n'avait pas résilié le contrat en vue d'empêcher la naissance de l'indemnité de licenciement. Le demandeur, employé de la banque depuis 26 ans, y avait d'ailleurs en principe droit en cas de licenciement ordinaire. Ce cas de figure ne correspond donc pas à la situation visée à l'art. 336 al. 1 let. c CO, ni du reste à aucun autre état de fait mentionné expressément à l'<ref-law>. Il reste donc à examiner si le licenciement du demandeur peut être tenu pour abusif pour un autre motif que ceux découlant expressément de cette disposition.
4.2 L'énumération prévue dans la loi n'est pas exhaustive (cf. <ref-ruling> consid. 2a; <ref-ruling> consid. 3b). Elle concrétise avant tout l'interdiction générale de l'abus de droit et en aménage les conséquences juridiques pour le contrat de travail. D'autres situations constitutives de congé abusif sont donc également admises par la pratique (cf. Rehbinder/Portmann, Commentaire bâlois, N 22 ss ad <ref-law>). Elles doivent toutefois comporter une gravité comparable aux cas expressément mentionnés à l'<ref-law> (arrêt 4C.174/2004 précité, consid. 2.1 et les arrêt cités).
L'abus de la résiliation peut découler non seulement des motifs du congé, mais également de la façon dont la partie qui met fin au contrat exerce son droit (<ref-ruling> consid. 4b/bb p. 166 confirmé in <ref-ruling> consid. 2b). Lorsqu'une partie résilie de manière légitime un contrat, elle doit exercer son droit avec des égards. Elle ne peut en particulier jouer un double jeu, contrevenant de manière caractéristique au principe de la bonne foi (<ref-ruling> consid. 2b; <ref-ruling> consid. 4b/cc p. 167). Ainsi, un comportement violant manifestement le contrat, par exemple une atteinte grave au droit de la personnalité dans le contexte d'une résiliation, peut faire apparaître cette dernière comme abusive. En revanche, un comportement qui ne serait simplement pas convenable ou indigne des relations commerciales établies ne suffit pas. Il n'appartient pas à l'ordre juridique de sanctionner une attitude seulement incorrecte (arrêt 4C.174/2004 précité, consid. 2.1 in fine). Par exemple, le fait pour l'employeur d'avoir affirmé à son collaborateur qu'il ne serait pas licencié et de lui notifier son congé une semaine plus tard est un comportement qui n'est certes pas correct, mais qui ne rend pas à lui seul le congé abusif (consid. 3b non publié de l'<ref-ruling>, traduit in SJ 2002 I p. 389).
Il faut souligner que l'interdiction de l'abus de droit au sens de l'<ref-law> réprime bien davantage que de simples chicanes; elle ne suppose en revanche pas que celui qui abuse de son droit ait l'intention de nuire ni que le procédé utilisé soit lui-même immoral (Mayer-Maly, Commentaire bâlois, éd. 1996, N 8 ad <ref-law>). Il peut ainsi y avoir abus de droit en cas de disproportion évidente des intérêts en présence, en particulier lorsque la norme applicable a justement pour but de mettre en place une certaine balance des intérêts (Merz, Commentaire bernois, N 371 ss ad <ref-law>). Tel est le cas de l'<ref-law>, dès lors que la résiliation abusive du contrat de travail exprime une limitation légale à la liberté contractuelle de celui qui met fin au contrat, afin de protéger le cocontractant qui a, pour sa part, un intérêt au maintien de ce même contrat (Vischer, Commentaire zurichois, N 2 ad <ref-law>). L'idée sous-jacente est avant tout d'offrir une protection sociale au salarié licencié abusivement, dès lors que la protection du congé n'a pas de portée pratique pour l'employeur (Vischer, op. cit., N 4 ad <ref-law>; Rehbinder, Commentaire bernois, N 3 ad <ref-law>).
Hormis les cas de disproportion des intérêts, l'abus peut aussi résulter de l'exercice d'un droit contrairement à son but (cf. Baumann, Commentaire zurichois, N 354 ad <ref-law>; Merz, Commentaire bernois, N 316 ad <ref-law>). Pour déterminer quel est le but poursuivi par une disposition légale, il convient notamment de tenir compte des intérêts protégés. Chacun peut s'attendre à ce que les droits dont il doit supporter l'exercice n'aillent pas à l'encontre du but visé par la disposition légale qui les met en oeuvre (Merz, op. cit., N. 51 ad <ref-law>; Meier-Hayoz, Commentaire bernois, N 192 ss ad <ref-law>). Sous cet angle également, l'intérêt légitime du salarié au maintien du contrat doit donc être pris en compte lors de l'examen du caractère abusif du congé donné par l'employeur. Ainsi, un licenciement pour simple motif de convenance personnelle peut être qualifié d'abusif (cf. Aubert, L'abus de droit en droit suisse du travail, in L'abus de droit, Saint-Etienne 2001, p. 101 ss, 109). Le fait qu'en droit suisse, l'existence d'une résiliation abusive ne conduise en principe pas à son invalidation, mais seulement à une indemnisation versée à celui qui en est victime ne change pas l'appréciation du point de savoir si le licenciement s'est exercé conformément à son but.
Il convient donc d'examiner, à l'aune de ces principes, si le licenciement du demandeur peut être qualifié d'abusif compte tenu des circonstances d'espèce (cf. <ref-ruling> consid. 3d p. 63).
4.3 Comme il l'a déjà été indiqué, les motifs du congé relèvent du fait et ne peuvent être revus dans le cadre de la présente procédure (cf. supra consid. 3.2). Il ne sera donc pas entré en matière sur l'argumentation de la défenderesse dans la mesure où celle-ci prétend que le licenciement ne serait pas abusif en se fondant sur d'autres motifs de congé que ceux retenus dans l'arrêt attaqué.
Si l'on s'en tient aux constatations cantonales, il apparaît que le demandeur a été licencié en regard de sa position hiérarchique supérieure, pour sauvegarder l'image de la défenderesse ternie par l'affaire B._, parce qu'il fallait un responsable, un "fusible". La banque n'est en revanche pas parvenue à démontrer l'existence de manquements de la part de son directeur général adjoint. Les juges ont relevé au contraire que le demandeur, employé pendant plus de 26 ans par la défenderesse, avait obtenu de longs et élogieux états de service et que la banque n'avait jamais formulé de reproche à son encontre avant la lettre de licenciement. La défenderesse a du reste remis au demandeur, un certificat de travail intermédiaire au 31 décembre 2000 mettant en évidence ses compétences de direction et le directeur général a lui-même admis que les mesures appropriées avaient été prises dès le moment où le demandeur avait été mis au courant des agissements de l'employé escroc. Enfin, le rapport interne de la banque ne signalait aucune faute relevant de la compétence du directeur adjoint.
Contrairement à ce que soutient la défenderesse, un tel licenciement apparaît comme abusif. En effet, en congédiant le demandeur, la banque a exclusivement cherché à préserver ses propres intérêts et à sauvegarder son image auprès des tiers, ternie par les détournements commis par l'un de ses employés. Pour atteindre cet objectif, il fallait qu'elle donne l'impression d'avoir pris les mesures adéquates, afin d'éviter que de telles irrégularités ne se reproduisent, c'est pourquoi elle a licencié le demandeur, en sa qualité de supérieur hiérarchique. La coïncidence entre les événements implique que, dans les milieux bancaires de la place, le demandeur n'a pu qu'inévitablement apparaître lié, d'une manière ou d'une autre, aux irrégularités commises par l'employé escroc, alors qu'il a précisément été retenu qu'aucun reproche ne pouvait lui être adressé à cet égard. Un tel procédé constitue une atteinte à la personnalité du demandeur de la part de la défenderesse qui, en sa qualité d'employeur, se devait au contraire de la protéger (<ref-law>). En définitive, la défenderesse a agi par pure convenance personnelle, faisant abstraction de l'intérêt légitime du demandeur à conserver un emploi qu'il occupait depuis plus de 26 ans à l'entière satisfaction de la banque, sans hésiter à ternir de manière imméritée la réputation personnelle et professionnelle de ce cadre auprès d'autres employeurs potentiels. Un congé donné dans ce contexte ne saurait être couvert par la liberté du licenciement.
Dans ces circonstances, on ne voit pas que la cour cantonale ait violé l'<ref-law> en qualifiant la résiliation du contrat de travail en cause d'abusive.
Enfin, l'indemnité allouée en vertu de l'<ref-law>, qui n'est du reste pas remise en cause dans la présente procédure, a été fixée conformément au droit fédéral (cf. ATF <ref-ruling> consid. 6a, 391 consid. 3).
Le recours doit par conséquent être rejeté.
5. Comme la valeur litigieuse, selon les prétentions du demandeur à l'ouverture de l'action (<ref-ruling> consid. 5b p. 41; <ref-ruling> consid. a), dépasse largement 30'000 fr., la procédure n'est pas gratuite (art. 343 al. 2 et 3 CO).
Compte tenu de l'issue du litige, les frais et dépens seront mis à la charge de la défenderesse (art. 156 al. 1 et 159 al. 1 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Un émolument judiciaire de 8'500 fr. est mis à la charge de la
défenderesse.
3. La défenderesse versera au demandeur une indemnité de 9'500 fr.
4. Le présent arrêt est communiqué en copie aux mandataires des parties et à la Cour d'appel de la juridiction des prud'hommes du canton de Genève.
Lausanne, le 6 juillet 2005
Au nom de la Ire Cour civile
du Tribunal fédéral suisse
Le président: La greffière: