Faits:
A. Engagé en 1986 par la banque Y._ SA en qualité de collaborateur, et devenu fondé de pouvoir dès le 1er janvier 1998, X._ (ci-après: l'employé ou le demandeur) a été soupçonné de malversations dès l'été 1998.
Après avoir été interrogé par des enquêteurs internes le 9 octobre 1998, l'employé a été suspendu dès le 15 octobre 1998, puis licencié avec effet immédiat le 27 novembre 1998. Il s'est aussitôt opposé à son licenciement, dont les motifs lui ont été communiqués, à sa demande, le 14 décembre 1998. En substance, son employeur lui a reproché d'avoir favorisé une connaissance, au détriment d'autres clients, dans l'attribution de produits dérivés nommés "xxx".
Le 13 janvier 1999, la banque a porté plainte contre son ex-employé, en même temps que contre son collègue A._, lequel avait admis diverses irrégularités. La banque déclarait cette plainte complémentaire à celle qu'elle avait déjà déposée le 16 juin 1998 contre B._, pour des faits de même nature.
L'instruction pénale a été extrêmement longue. En 2000 déjà, cependant, les trois clients que la plaignante désignait comme lésés ont déclaré qu'ils ne reprochaient rien au prévenu. Celui-ci a alors demandé la disjonction des causes, avec préavis de non-lieu, mais le juge d'instruction alors saisi a rejeté cette requête le 10 mai 2001, avec confirmation par la Chambre d'accusation le 6 septembre 2001. Selon le rapport d'expertise délivré le 17 juillet 2003, il n'est pas établi que le prévenu aurait systématiquement favorisé un client au détriment de trois autres. Les investigations menées dans les années suivantes (et notamment une expertise complémentaire portant essentiellement sur les actes de B._) n'ont pas apporté de nouvel éclaircissement décisif au sujet du prévenu.
Malgré la demande du prévenu, du 27 janvier 2006, qu'un non-lieu soit prononcé en sa faveur, son renvoi devant le Tribunal pénal économique a été préavisé par le juge d'instruction le 25 septembre 2006, en même temps que ceux de B._ et A._, ce dernier ayant confirmé ses aveux de malversations devant le juge d'instruction déjà le 12 mai 1999.
A l'audience du Tribunal pénal économique, le procureur a conclu à l'acquittement du demandeur, la banque concluant à sa condamnation, tout en s'en remettant à l'appréciation du tribunal quant à la quotité de la peine.
Par jugement du 18 avril 2008, le Tribunal pénal économique a acquitté "purement et simplement" l'ex-employé en laissant sa part de frais à charge de l'Etat. En substance, il a considéré qu'il n'y avait pas de "démonstration d'un comportement frauduleux de la part de X._", malgré certaines saisies tardives dans le système informatique de la banque (soit à un moment où les gains ou les pertes étaient scellés), non constitutives en elles-mêmes d'une infraction.
B. Le 30 septembre 2009, le demandeur a ouvert action contre la banque, principalement en paiement de 321'769 fr. 95. Les postes les plus importants du dommage se distinguent comme suit: 61'533 fr. 20 de salaire (couvrant le délai de congé de six mois); 45'000 fr. de primes de performance pour l'année 1998 et le premier semestre 1999; 48'083 fr. 25 d'indemnité de licenciement, en vertu de la convention relative à la suppression d'emploi ...; 52'000 fr. d'indemnité pour congé immédiat injustifié selon l'art. 337c al. 3 CO; 50'000 fr. d'indemnité de tort moral; 53'800 fr. de frais d'avocat pour la procédure pénale.
Dans sa réponse, la défenderesse a en particulier reconnu devoir à son ex-employé la somme de 40'696 fr. 65, soit l'équivalent de trois mois de salaire.
Par jugement du 19 mai 2011, le juge instructeur de la Ire Cour civile du Tribunal cantonal neuchâtelois, statuant comme juge unique, a notamment condamné la défenderesse à verser au demandeur le montant brut de 39'476 fr. 60 et net de 1'200 fr. (en couverture des prétentions de salaires et accessoires durant un délai de résiliation de trois mois), ainsi qu'une indemnité de 52'000 fr. (basée sur l'art. 337c al. 3 CO). Elle a rejeté toute autre prétention.
Sur appel du demandeur, la Cour d'appel civile du Tribunal cantonal neuchâtelois, par arrêt du 19 mars 2012, a confirmé le jugement attaqué, en considérant toutefois que la défenderesse devait encore verser à sa partie adverse le montant de 19'000 fr. à titre de prime (bonus) pour l'année 1998.
C. Le demandeur exerce un recours en matière civile contre l'arrêt cantonal du 19 mars 2012. Demandant son annulation partielle, le recourant conclut à ce que la défenderesse soit condamnée à lui payer, en plus des postes déjà admis par la cour cantonale, 50'000 fr. à titre d'indemnité pour tort moral, ainsi que 53'800 fr. à titre de dédommagement pour les frais de mandataire encourus dans la procédure pénale. Subsidiairement, il conclut au renvoi de la cause à l'autorité cantonale pour nouvelle décision et, en tout état de cause, à la condamnation de la défenderesse aux frais et dépens.
L'intimée conclut, sous suite de dépens, au rejet du recours.

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé partiellement dans ses conclusions en paiement (art. 76 al. 1 LTF) et dirigé contre un arrêt final (art. 90 LTF) rendu en matière civile (art. 72 al. 1 LTF) par une autorité cantonale de dernière instance (art. 75 LTF) dans une affaire pécuniaire en matière de droit du travail dont la valeur litigieuse atteint le seuil de 15'000 fr. (art. 74 al. 1 let. a LTF), le recours est en principe recevable puisqu'il a été déposé dans le délai (art. 48 al. 1 et 100 LTF) et la forme (art. 42 LTF) prévus par la loi.
1.2 Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF.
Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF). Il n'est limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.4 p. 317 s.; <ref-ruling> consid. 1.4 et l'arrêt cité). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (art. 108 al. 1 let. b LTF), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 1.3 p. 584; <ref-ruling> consid. 2.2.1 p. 389; <ref-ruling> consid. 1.4).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 5.1 p. 356) - ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF). En l'espèce, le recourant n'invoque pas l'arbitraire dans l'établissement des faits et il n'y a pas lieu de s'écarter de l'état de fait dressé par l'autorité précédente.
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (art. 107 al. 1 LTF). Toute conclusion nouvelle est irrecevable (art. 99 al. 2 LTF).
2. 2.1 La cour cantonale juge, au regard de l'ensemble des circonstances d'espèce, que l'intimée doit être condamnée à verser au recourant l'indemnité maximale (six mois de salaire) autorisée par l'art. 337c al. 3 CO. Elle considère par contre que l'atteinte subie par le recourant n'est pas telle qu'elle exigerait une réparation supplémentaire sous l'angle de l'art. 49 CO.
Insistant en particulier sur l'atteinte grave à sa personnalité résultant de la procédure pénale mise en ?uvre par l'intimée, le recourant conteste le raisonnement de la cour précédente, estimant qu'une indemnité supplémentaire pour tort moral de 50'000 fr. doit lui être attribuée.
2.2 L'art. 337c al. 3 CO prévoit qu'en cas de résiliation immédiate injustifiée, le juge peut allouer au travailleur une indemnité dont il fixera librement le montant, en tenant compte de toutes les circonstances, mais sans dépasser l'équivalent de six mois de salaire.
Cette indemnité, qui s'ajoute aux droits découlant de l'art. 337c al. 1 CO, revêt une double finalité, à la fois réparatrice et punitive, quand bien même elle ne consiste pas en des dommages-intérêts au sens classique, car elle est due même si la victime ne subit ou ne prouve aucun dommage; revêtant un caractère sui generis, elle s'apparente à la peine conventionnelle (<ref-ruling> consid. 3.1 p. 407; <ref-ruling> consid. 9b p. 214; cf. arrêt 4C.86/2001 du 28 mars 2002 consid. 1a).
L'indemnité est fixée d'après la gravité de la faute de l'employeur, la mesure de l'atteinte portée aux droits de la personnalité du travailleur et la manière dont la résiliation a été annoncée; d'autres critères tels que la durée des rapports de travail, l'âge du lésé, sa situation sociale, une éventuelle faute concomitante et les effets économiques du licenciement entrent aussi en considération (arrêt 4A_660/2010 du 11 mars 2011 consid. 3.2 et les références).
Statuant selon les règles du droit et de l'équité (art. 4 CC), le juge dispose d'un large pouvoir d'appréciation. Le Tribunal fédéral ne substitue qu'avec retenue sa propre appréciation à celle de la juridiction cantonale. Il n'intervient que si la décision s'écarte sans raison des règles établies par la doctrine et la jurisprudence en matière de libre appréciation, ou lorsqu'elle repose sur des faits qui, dans le cas particulier, ne devaient jouer aucun rôle, ou encore lorsqu'elle n'a pas tenu compte d'éléments qui auraient absolument dû être pris en considération; en outre, il sanctionnera les décisions rendues en vertu d'un pouvoir d'appréciation lorsqu'elles aboutissent à un résultat manifestement injuste ou à une iniquité choquante (cf. <ref-ruling> consid. 4.1 p. 32; <ref-ruling> consid. 3.1 p. 220; <ref-ruling> consid. 2 p. 382).
2.3 Selon la jurisprudence, l'allocation et l'évaluation d'une indemnité à verser en application de l'art. 49 al. 1 CO dépendent avant tout de la gravité des souffrances causées par l'atteinte à la personnalité, et de la possibilité de l'adoucir sensiblement par le versement d'une somme d'argent (<ref-ruling> consid. 2.2.2 p. 309; <ref-ruling> consid. 5.1 p. 704). Une indemnité est par exemple due au travailleur qui a été victime, dans l'entreprise de l'employeur, de harcèlement psychologique ou mobbing, lorsque, d'un point de vue objectif, il a subi une humiliation particulièrement sévère (<ref-ruling> consid. 3a p. 74 s.; voir aussi ATF <ref-ruling> consid. 5.1 p. 704; récemment: arrêt 4A_607/2011 du 10 novembre 2011 consid. 3).
Là également, le juge apprécie selon les règles du droit et de l'équité (art. 4 CC) si une indemnité se justifie au regard des circonstances particulières de la cause (<ref-ruling> consid. 4.4 p. 725; récemment: arrêt 4A_578/2011 du 12 janvier 2012 consid. 6.2). Le Tribunal fédéral ne contrôle qu'avec réserve une décision d'équité prise en dernière instance cantonale (cf. supra consid. 2.2).
Comme on l'a déjà indiqué, l'indemnité prévue à l'art. 337c al. 3 CO n'a pas pour seule fonction de punir l'auteur du congé abusif; elle vise également la réparation du tort moral subi par le travailleur licencié (cf. arrêts 4C.84/2005 du 16 juin 2005 consid. 5.1; 4C.86/2001 déjà cité consid. 2a; 4C.310/1998 du 8 janvier 1999 consid. 4a publié in SJ 1999 I 277). Du fait de sa finalité réparatrice, ladite indemnité ne laisse guère de place à l'application cumulative de l'art. 49 CO, car elle embrasse toutes les atteintes à la personnalité du travailleur qui découlent de la résiliation abusive du contrat (arrêt 4C.310/1998 déjà cité consid. 4a).
Demeure réservée l'hypothèse dans laquelle une telle atteinte serait à ce point grave qu'un montant correspondant à six mois de salaire ne suffirait pas à la réparer. Sous cette réserve, l'application de l'art. 49 CO, parallèlement à l'art. 337c al. 3 CO, ne saurait entrer en ligne de compte que dans des circonstances exceptionnelles. On songe ici, par exemple, à des reproches de type diffamatoire, n'ayant aucun lien de connexité avec la relation de travail, que l'employeur adresserait au travailleur à l'occasion de son licenciement ou encore au dénigrement du second par le premier vis-à-vis de tiers et notamment des employeurs potentiels du travailleur congédié (arrêt 4C.86/2001 déjà cité consid. 2a; 4C.310/1998 déjà cité consid. 4).
2.4 Le recourant soutient en substance que, en estimant que les atteintes qu'il a subies (y compris la souffrance morale) sont réparées par l'indemnité correspondant à six mois de salaire, la cour cantonale a mal apprécié les circonstances; selon lui, l'autorité précédente devait considérer qu'une réparation supplémentaire s'imposait.
En lien avec les atteintes à la personnalité du recourant qui découlent de la résiliation injustifiée du 27 novembre 1998 (pour les atteintes résultant d'une autre cause, cf. infra consid. 2.5), on ne voit toutefois pas que la cour cantonale aurait omis de tenir compte de faits déterminants. Pour fixer l'indemnité maximale prévue par l'art. 337c al. 3 CO, elle a relevé que le recourant avait travaillé douze ans au service du même employeur, à la satisfaction très manifeste de celui-ci. L'autorité précédente a en particulier tenu compte des accusations (ayant conduit au licenciement immédiat) qui se sont révélées infondées, des circonstances du licenciement qui comportaient une "certaine dureté psychologique" (relative absence d'écoute aux explications de l'employé et absence de motifs précis, au moment de sa suspension), ainsi que des conséquences de la résiliation injustifiée sur la santé de l'employé (soit un état "anxio-dépressif et tensionnel" attesté par son médecin traitant). Toujours en se fondant sur les critères d'appréciation fixés par la jurisprudence, elle a également examiné les conséquences économiques du licenciement, soulignant qu'après une période de chômage de quelques mois, le recourant a fondé sa propre société, ce qui lui a permis de retrouver une situation professionnelle comparable.
Concernant ce dernier critère, il faut observer que le temps que l'employé met à exercer une nouvelle activité est propre à aggraver l'atteinte causée par le congé injustifié et qu'il peut à ce titre être pris en considération (arrêt 4A_660/2010 du 11 mars 2011 consid. 3.1 et 3.3). Ainsi, contrairement à ce que laisse entendre le recourant, l'autorité précédente, dans l'examen des effets économiques du licenciement, était en droit de tenir compte du fait qu'il avait retrouvé relativement rapidement une activité professionnelle comparable à celle qu'il exerçait auprès de l'intimée.
L'indemnité maximale autorisée par l'art. 337c al. 3 CO a été octroyée au recourant. Il n'apparaît pas que l'autorité précédente ait pris une décision choquante ou inéquitable en estimant que l'atteinte n'était pas grave, au sens de la jurisprudence précitée, au point que cette indemnité maximale ne suffisait pas à la réparer. Dans une situation comparable (cause 4C.86/2001), la Cour de céans avait d'ailleurs abouti à la même conclusion. Il était alors question d'un employé, ayant travaillé pendant plus de quinze ans pour son employeur, qui a dénoncé - à juste titre - le non-respect par certains chefs de service de prescriptions concernant la durée du travail ou la sécurité dans l'exploitation. Cet employé a fait l'objet de toute sorte de reproches dont certains se sont révélés discutables voire mal fondés; son licenciement s'est déroulé de manière relativement humiliante; la défenderesse a pris pour prétexte la plainte d'un usager pour le licencier, sans lui permettre de s'exprimer, n'offrant aucun espace de discussion; par ailleurs le licenciement a eu de sérieuses répercussions sur la santé de l'employé qui a souffert d'un état anxio-dépressif important et inquiétant à l'annonce de son futur licenciement; il a aussi eu de lourdes conséquences économiques puisque le travailleur s'est retrouvé au chômage et qu'il ne semble pas avoir pu reprendre rapidement une nouvelle activité professionnelle (arrêt cité consid. 1e); l'atteinte à la personnalité de l'employé a été considérée comme grave et une indemnité correspondant à six mois de salaire lui a été octroyée. La Cour de céans a alors observé qu'aucun des motifs pouvant justifier l'application de l'art. 49 CO n'a été constaté et que l'atteinte à la personnalité du travailleur se rattachait strictement au motif du licenciement, à ses modalités et à ses conséquences (arrêt cité consid. 2b).
Compte tenu de la retenue avec laquelle le Tribunal fédéral substitue sa propre appréciation à celle de la juridiction cantonale, on ne voit donc pas que l'autorité précédente ait transgressé le droit fédéral en n'accordant pas, sous l'angle de l'art. 49 CO, une réparation supplémentaire à celle déjà octroyée sur la base de l'art. 337c al. 3 CO, étant encore précisé que les désagréments subis par le recourant par suite de la procédure pénale ne peuvent être considérés comme résultant de la résiliation injustifiée (cf. infra consid. 2.5).
Compte tenu de la retenue avec laquelle le Tribunal fédéral substitue sa propre appréciation à celle de la juridiction cantonale, on ne voit donc pas que l'autorité précédente ait transgressé le droit fédéral en n'accordant pas, sous l'angle de l'art. 49 CO, une réparation supplémentaire à celle déjà octroyée sur la base de l'art. 337c al. 3 CO, étant encore précisé que les désagréments subis par le recourant par suite de la procédure pénale ne peuvent être considérés comme résultant de la résiliation injustifiée (cf. infra consid. 2.5).
2.5 2.5.1 Selon les constatations cantonales, le préjudice subi par le recourant ne résulte toutefois pas seulement de la résiliation injustifiée proprement dite (arrêt entrepris p. 9; cf. déjà : jugement de première instance p. 17), mais également d'une autre cause, soit de la procédure pénale menée à son encontre (et mise en ?uvre plusieurs semaines après la résiliation injustifiée). L'autorité précédente fait d'ailleurs référence à la souffrance morale de l'ex-employé, laissant entendre que l'angoisse ressentie par celui-ci, dépassant "clairement les conséquences nécessairement liées à une résiliation de contrat injustifiée", trouve son origine dans les comparutions, qui lui rappelaient ses problèmes professionnels.
Il ressort indéniablement des constatations cantonales que la procédure pénale a causé une souffrance réelle au recourant. Plus précisément, on observe à la lecture de l'arrêt entrepris que la souffrance ressentie par l'ex-employé est due à la longueur extrême de la procédure, et en particulier aux comparutions qui ont jalonné celle-ci (arrêt entrepris p. 9).
Cette cause ne saurait être ignorée et il convient de déterminer si le cas d'espèce supposait l'application cumulative de l'art. 49 CO, en raison de circonstances n'étant plus directement rattachées à la résiliation injustifiée (cf. <ref-ruling> consid. 3c; arrêt 4C.86/2001 déjà cité consid. 2b; HARDY LANDOLT, Zürcher Kommentar, 3e éd. 2007, no 879 ad art. 49 CO et les nombreuses références; ROLAND BREHM, Berner Kommentar, 3e éd. 2006, no 76a ad art. 49 CO).
Il s'agit alors d'examiner si c'est bien en raison du comportement illicite de l'intimée que le préjudice a été causé (sur la nécessaire réalisation des conditions de l'art. 41 CO dans un cas d'application basé sur l'art. 49 CO: <ref-ruling> consid. 2e p. 209 s.; BREHM, op. cit., no 13 ad art. 49 CO; LANDOLT, op. cit., no 92 ad art. 49 CO).
2.5.2 En l'espèce, il résulte des constatations cantonales - qui lient le Tribunal fédéral (art. 105 al. 1 LTF) - que les premiers soupçons de l'intimée à l'encontre du recourant étaient légitimes. Contrairement à ce que soutient le recourant, il n'importe à cet égard qu'il n'aurait pas été poursuivi pénalement sans le dépôt de la plainte de l'intimée. On ne saurait en tout cas considérer que celle-ci a déposé une plainte pénale contre son ex-employé (et donc mis en ?uvre la procédure pénale) en sachant que sa démarche était vouée à l'échec (cf. arrêt 4C.353/2002 du 3 mars 2003 consid. 5.1). Certes, la cour cantonale a constaté que, rétrospectivement, la position de plaignante de l'intimée à l'encontre du recourant "apparaît très discutable, quoi qu'ait pu en dire à l'époque la Chambre d'accusation". Toutefois, l'ouverture d'une action, même objectivement injustifiée, ne saurait, à elle seule, engager la responsabilité de celui qui en est à l'origine (<ref-ruling> consid. 4 p. 398). L'intimée n'étant, lorsqu'elle a déposé plainte, pas de mauvaise foi, elle pouvait confier la défense de ses droits présumés aux autorités de poursuite pénale sans que l'on puisse parler d'une atteinte illicite à la personnalité du recourant susceptible de justifier l'octroi d'une indemnité pour tort moral (cf. <ref-ruling>, ibidem).
2.5.3 S'agissant du maintien des accusations de la banque au cours de la procédure pénale, la cour cantonale a retenu que, depuis le rapport d'expertise de 2003, cette position n'était plus défendable. Il ressort cependant également de l'arrêt cantonal que les autorités de poursuite pénale, qui avaient à disposition le même rapport, ont toujours refusé, jusqu'au renvoi devant le juge de siège, de prononcer un non-lieu. Cela étant, si l'on peut certainement reprocher à l'intimée d'avoir trop longtemps maintenu un amalgame entre la situation du recourant et celle des autres prévenus (plutôt que d'admettre qu'elle n'avait pas de preuve de sa culpabilité [arrêt entrepris p. 15]), il est par contre délicat de qualifier d'emblée ce comportement d'illicite. La question peut toutefois rester indécise, la condition du lien de causalité faisant ici quoi qu'il en soit défaut.
S'agissant du lien de causalité naturelle, qui relève des constatations de fait (<ref-ruling> consid. 2; <ref-ruling> consid. 2c/ee; <ref-ruling> consid. 5b), il s'agissait de démontrer que la souffrance morale subie par le recourant, due à la procédure pénale, trouvait son origine dans le comportement de la banque.
A cet égard, il est établi que l'extrême longueur de la procédure pénale n'est pas due à l'attitude de l'intimée, qui a au contraire requis à plusieurs reprises sa progression plus rapide et a même déposé, le 10 décembre 2004, un recours pour retard injustifié, retiré vu la reprise des opérations (arrêt entrepris p. 10). Partant, on ne saurait reprocher à l'intimée d'avoir tiré, par l'utilisation de divers incidents de procédure, le procès en longueur. Dans cette perspective, la souffrance du recourant découlant de la longueur de la procédure pénale ne peut être considérée comme résultant du comportement de l'intimée.
Il reste à déterminer si le maintien des accusations portées par la banque à l'encontre du prévenu a causé le dommage évoqué. Il s'agissait alors d'établir que les autorités de poursuite pénale, instruisant des infractions se poursuivant d'office, se sont fondées de manière déterminante sur ces accusations (pour les détails cf. arrêt 4C.77/2001 du 12 septembre 2001 consid. 2d/aa publié in SJ 2002 I p. 9).
Il est constant que, si l'intimée a maintenu l'amalgame entre le comportement du recourant et ceux de B._ et A._, elle n'a pas usé de machinations dans le but de créer une apparence de culpabilité, de façon à pousser les autorités pénales à poursuivre la procédure.
Il n'est en outre pas établi que le seul maintien des accusations de la plaignante aurait eu pour effet d'influencer les autorités de poursuite pénale, de sorte que celles-ci, plutôt que d'opter pour le non-lieu, auraient décidé de poursuivre la procédure et de renvoyer le recourant devant le Tribunal pénal économique. Certes, la cour cantonale a jugé "peu probable (...) que le Ministère public ait repris complètement l'examen du dossier, au moment déjà du renvoi des prévenus en instance de jugement, vu le préavis non différencié qui lui avait été transmis par la juge d'instruction" (arrêt cantonal p. 10). Ce constat est impropre à démontrer que le procureur général aurait prononcé un non-lieu si l'intimée n'avait pas maintenu ses accusations. Il faut à cet égard relever que, même à considérer que le Ministère public n'a pas repris l'examen complet du dossier avant le renvoi, il n'en demeure pas moins que celui-ci a été décidé sur la base d'un préavis du juge d'instruction. Certes, la cour cantonale indique que la position de la plaignante n'était plus défendable. Le juge d'instruction, dans son préavis, et à sa suite le Ministère public, ont toutefois apprécié la situation de façon différente (en tout cas à cette époque puisqu'ensuite le Ministère public, en audience de jugement, a conclu à l'acquittement du prévenu) et il n'est pas démontré que, dans le cadre de cette appréciation, ils auraient été influencés de façon déterminante par l'intimée.
Il ne résulte donc pas des constatations souveraines de l'autorité cantonale que le recourant aurait apporté la preuve que, sans le maintien des accusations de l'intimée, un non-lieu aurait été prononcé et que la procédure pénale (et donc les comparutions jalonnant celles-ci), à l'origine de ses souffrances, aurait pris fin plus rapidement.
L'existence d'un lien de causalité naturelle n'a pas été démontrée et l'art. 49 CO ne saurait trouver application en l'espèce.
3. 3.1 L'autorité cantonale retient que les frais assumés par le recourant pour sa défense dans la procédure pénale ne peuvent être mis à la charge de l'intimée, celle-ci n'ayant commis aucun acte illicite au sens de l'art. 41 CO. En substance, elle considère qu'en procédure pénale, particulièrement lorsque celle-ci a trait à une poursuite d'office, l'intervention du Ministère public comme accusateur principal ne laisse plus guère de place à un acte illicite. Elle réserve toutefois l'hypothèse d'une dénonciation calomnieuse, notamment si celle-ci s'accompagne d'une machination destinée à créer une apparence de culpabilité; cette hypothèse n'est, selon elle, pas réalisée ici.
Le recourant soutient que l'intimée, en raison des "comportements qu'elle a adoptés à l'encontre de son ex-employé, a engagé sa responsabilité". Se fondant sur divers précédents (notamment: arrêts 1C_10/2007 du 12 juillet 2007 consid. 4.1; 4C.195/2001 du 12 mars 2002 consid. 2b/bb), il est d'avis que les frais d'avocat doivent être considérés comme un élément du dommage que le responsable doit réparer.
En l'espèce, on ne peut toutefois réfléchir en fonction de pertes patrimoniales (frais d'avocat) qui constitueraient un élément du dommage (que le responsable doit indemniser), mais le fondement de la responsabilité doit être recherché dans le procès (pénal) lui-même (sur la distinction: <ref-ruling> consid. 3 p. 395 ss).
On constate ainsi d'emblée qu'il n'est pas nécessaire de se demander si le recourant qui prétend à une indemnisation aurait déjà pu se voir accorder des dépens pour les frais engagés dans la procédure pénale, cette question se posant précisément lorsque les frais d'avocat représentent un élément du dommage (cf. <ref-ruling> consid. 3a p. 396; récemment: arrêt 4A_127/2011 du 12 juillet 2011 consid. 12.2).
3.2 C'est ainsi à juste titre que la cour cantonale a observé que la participation du recourant à la procédure pénale occasionne elle-même le dommage et qu'il s'agit de se demander si celui-ci résulte d'un comportement illicite de l'autre partie. Le fondement de cette responsabilité repose en principe sur l'art. 41 CO.
Dans l'<ref-ruling>, le Tribunal fédéral s'est demandé si l'action ouverte devait constituer la violation d'une norme de comportement (cf. dans ce sens: <ref-ruling> consid. 9 p. 183; <ref-ruling> consid. 4 p. 280 s.). Il a laissé la question indécise considérant que, quoi qu'il en soit, la responsabilité suppose un comportement contraire aux moeurs, intentionnel ou dû à une négligence grave, au sens de l'art. 41 CO. Engage ainsi sa responsabilité celui qui ouvre abusivement un procès ou se comporte dans le procès d'une manière malveillante ou contraire à la bonne foi, peu importe que ce comportement tombe ou non sous le coup de la loi pénale (<ref-ruling> consid. 4; arrêt 4C.77/2001 déjà cité consid. 2a/aa). Une faute légère, qui aurait conduit à une appréciation erronée d'une situation juridique, ne peut donner lieu à des dommages-intérêts. Cette appréciation n'a que les conséquences prévues par le droit de procédure (<ref-ruling> consid. 4 p. 398 s.). Engage sa responsabilité celui qui, non seulement ouvre une action à la légère, mais sait d'emblée que sa position était dépourvue de toute chance (arrêt 4C.353/2002 déjà cité consid. 5.1); il en va de même de celui qui a tiré le procès en longueur, utilisant à dessein tous les incidents de procédure pour le compliquer (PIERRE TERCIER, L'indemnisation des frais d'avocat et l'assurance de protection juridique, in Journées du droit de la circulation routière, 1994, p. 12).
3.3 Le raisonnement adopté plus haut (cf. supra consid. 2.5) peut être repris ici mutatis mutandis.
On ne saurait inférer du dépôt d'une plainte pénale un comportement illicite de l'intimée, ses soupçons étant, à ce moment-là, légitimes (cf. supra consid. 2.5.2).
S'agissant du maintien des accusations de l'intimée au cours de la procédure pénale, la question de l'illicéité peut rester indécise et le cas résolu sur la base du lien de causalité naturelle (sur la nécessité d'établir ce lien pour fonder une responsabilité résultant d'un comportement abusif adopté en procédure, expressément: HUGO CASANOVA, Die Haftung der Parteien für prozessuales Verhalten, thèse Fribourg 1982, p. 72 s.). Il a déjà été indiqué plus haut (cf. infra consid. 2.5.3) qu'il n'a pas été établi que les autorités judiciaires se seraient fondées de manière déterminante sur les accusations maintenues par la banque en cours de procédure; il n'est ainsi pas démontré que la procédure pénale aurait été plus brève, en l'absence de l'intervention de la partie plaignante. On doit dès lors conclure que le lien de causalité entre le comportement de la banque et le dommage patrimonial subi (soit les frais d'avocat résultant d'une procédure pénale s'étendant jusqu'à l'audience de jugement) n'a pas été établi. Partant, la responsabilité de l'intimée ne peut être engagée.
Enfin, il n'est pas établi que la banque aurait, en particulier depuis la divulgation du rapport d'expertise de 2003, effectué des requêtes importantes ayant nécessité une activité de la part du mandataire de l'ex-employé qui irait au-delà de celle qu'il aurait dû de toute façon entreprendre en l'absence d'intervention de la partie plaignante. Le recourant, qui n'axe d'ailleurs pas son argumentation sous cet angle, n'a donc pas non plus apporté la preuve que le maintien des accusations de l'intimée lui aurait causé, dans cette perspective également, un dommage.
Le grief étant mal fondé, il n'y a pas lieu d'examiner le moyen tiré de la prescription dont se prévaut l'intimée, étant par ailleurs précisé qu'il est douteux que ce moyen, invoqué pour la première fois devant le Tribunal fédéral, soit recevable (cf. <ref-ruling> consid. 2.2 p. 226 s.; <ref-ruling> consid. 1c et d).
4. Il résulte des considérations qui précèdent que le recours doit être rejeté.
Les frais et dépens sont mis à la charge du recourant qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimée une indemnité de 2'500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Neuchâtel, Cour d'appel civile.
Lausanne, le 24 juillet 2012
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Piaget