Faits:
A. A partir de 1994, X._, qui travaillait précédemment comme employé de A._, s'est mis à son compte, sous l'enseigne U._, tout en demeurant dans les locaux qu'il occupait à Genève. A._ lui avait confié un mandat, intitulé V._, qui constituait l'essentiel de son activité.
Par contrat du 4 juillet 1996, A._ a remis à bail à X._, U._, des locaux commerciaux avec des places de parc dans le même immeuble. Conclu initialement du 1er juillet 1996 au 30 juin 1999, le bail était ensuite renouvelable tacitement d'année en année, sauf dénonciation par l'une des parties six mois à l'avance. Dans la clause permettant au bailleur de résilier le bail de manière anticipée, X._ a ajouté, à la main, qu'il fallait se référer aux conditions spéciales; à la fin du contrat, il a rédigé de sa main une clause qui contient notamment le passage suivant:
"Le bail peut être résilié par le locataire au cas où A._ termine ou ne reconduit pas le mandat V._ à U._ selon le document en copie signé par A._ le 16 décembre 1994."
Dans le contrat en possession de X._, cet ajout comporte le paraphe de l'assistante du représentant de A._. Il a été retenu qu'elle n'aurait pas apposé son paraphe sans l'accord de son supérieur, de sorte qu'il fallait admettre que A._ avait accepté l'adjonction faite par X._.
Au 1er décembre 1999, A._ a vendu ledit immeuble à la banque Y._ (ci-après: Y._).
En 2001, B._ Limited a repris l'actif et le passif de A._, puis C._ lui a succédé.
Le 28 mars 2003, C._ a informé X._ que le projet W._ prendrait fin au 30 juin 2003. Il a été retenu, à la suite de l'administration des preuves, que ce projet correspondait à celui précédemment intitulé V._.
Par courrier du 30 octobre 2003, X._ a résilié le bail pour le 30 novembre 2003, au motif que C._ avait décidé d'arrêter le programme W._.
Contestant que le locataire puisse se prévaloir de la clause additionnelle lui permettant de résilier le bail de façon anticipée, Y._ a accepté le congé pour l'échéance ordinaire, soit le 30 juin 2004 en tenant compte du préavis conventionnel de six mois.
X._ a quitté les lieux le 30 novembre 2003.
X._ soutenant qu'il avait valablement résilié le bail de façon anticipée et Y._ affirmant le contraire, les parties sont entrées en conflit, chacune se prétendant créancière de l'autre.
Dans une poursuite ouverte sur réquisition de Y._, la mainlevée provisoire de l'opposition a été refusée par arrêt du Président de la Cour des poursuites et faillites du Tribunal cantonal vaudois du 28 février 2005.
B. Le 14 mars 2006, X._ a saisi la Commission de conciliation en matière de baux et loyers du canton de Genève, réclamant à sa partie adverse 3'444 fr. 70 pour une partie du loyer payée par avance, ainsi que 35'000 fr. pour des frais d'avocat, des heures perdues et en guise de tort moral, sollicitant par ailleurs que la garantie de loyer qu'il a fournie soit libérée. Après l'échec de la tentative de conciliation, il a saisi le Tribunal des baux et loyers le 29 septembre 2006. Y._, de son côté, a formé une demande reconventionnelle, réclamant 1'293 fr. 60 à titre de prestations de services et 27'647 fr. 50 correspondant au loyer des mois de janvier à juin 2004.
Par jugement du 14 novembre 2007, le Tribunal des baux et loyers a condamné X._ à verser à Y._ le montant de 21'585 fr. avec intérêts à 7% dès le 15 février 2004. Il a rejeté la demande principale et admis la demande reconventionnelle, en excluant toutefois la facturation des services pour le motif que le locataire avait quitté les lieux.
Saisi d'un appel de X._ et d'un appel incident de Y._, la Cour de justice, par arrêt du 2 février 2009, a confirmé le jugement attaqué. Elle a considéré que X._ avait tardé à invoquer le motif de résiliation anticipée et qu'il était déchu de cette faculté.
C. X._ a déposé un recours en matière civile au Tribunal fédéral contre l'arrêt du 2 février 2009. Reprochant à la cour cantonale d'avoir violé le principe de l'autorité de chose jugée du jugement de mainlevée et d'avoir constaté arbitrairement l'intention réelle des parties, il reprend ses conclusions initiales avec suite de frais et dépens et demande, subsidiairement, le renvoi de la cause à l'autorité précédente.
L'intimée a conclu au rejet du recours dans la mesure où il est recevable avec suite de frais et dépens.

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé dans ses conclusions en paiement et dans ses conclusions libératoires (art. 76 al. 1 LTF), 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 dont la valeur litigieuse atteint le seuil de 15'000 fr. requis en matière de bail à loyer (art. 74 al. 1 let. a LTF), le recours est en principe recevable, puisqu'il a été déposé dans le délai (art. 100 al. 1 et 45 al. 1 LTF) et la forme (art. 42 LTF) prévus par la loi.
1.2 Le recours 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 donc 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.1 p. 104). 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.1 p. 105). Il ne peut toutefois entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (art. 106 al. 2 LTF).
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. 1.5 p. 130; <ref-ruling> consid. 4.3 p. 63 - ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF).
La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévues par l'art. 105 al. 2 LTF seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (cf. <ref-ruling> consid. 1.4 p. 140). Le recourant ne peut d'ailleurs demander une correction de l'état de fait que si celle-ci est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF). Aucun fait nouveau ni preuve nouvelle ne peut être présenté, à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF).
En l'espèce, le recourant expose longuement, à la manière d'une plaidoirie, sa propre version des faits. Dès lors qu'il n'invoque avec précision ni l'arbitraire, ni une violation du droit, pas plus qu'il n'essaie d'en apporter la démonstration, il n'y a pas lieu de tenir compte de l'état de fait qu'il a dressé et le raisonnement doit être conduit exclusivement sur la base des constatations cantonales.
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 Comme premier argument, le recourant soutient que l'arrêt attaqué ne serait pas conforme aux considérants contenus dans le jugement de mainlevée et violerait pour ce motif le principe de l'autorité de chose jugée.
Lorsque - comme c'est le cas en l'espèce - la prétention litigieuse relève du droit fédéral, le respect de l'autorité de chose jugée est une question de droit fédéral (<ref-ruling> consid. 2a p. 90 et les arrêts cités). Le Tribunal fédéral, saisi d'un recours en matière civile, peut donc examiner librement ce grief (art. 95 let. a et art. 106 al. 1 LTF).
L'autorité de chose jugée interdit qu'un même litige, c'est-à-dire un litige portant sur le même état de fait et le même fondement juridique, puisse être, alors qu'il a déjà été définitivement tranché, soumis à nouveau à un juge (<ref-ruling> consid. 2a p. 90; <ref-ruling> consid. 1b p. 272). Encore faut-il, pour que le juge postérieur soit lié, que la prétention ait été tranchée sur le fond.
Or, la décision qui accorde ou refuse la mainlevée, qu'il s'agisse d'une mainlevée provisoire ou d'une mainlevée définitive, est une pure décision d'exécution forcée dont le seul objet est de dire si la poursuite peut continuer ou si le créancier est renvoyé à agir par la voie d'un procès ordinaire; l'objet de la procédure, c'est-à-dire la question juridique posée, n'est pas la même que dans un procès sur le fond qui a pour but de dire si le droit invoqué existe ou n'existe pas (<ref-ruling> consid. 6c p. 85). La décision sur la demande de mainlevée n'est qu'un incident de la poursuite qui se distingue d'un procès ordinaire notamment par le fait que le juge ne statue que sur la base des pièces produites et selon le critère de la vraisemblance (<ref-ruling> consid. 4.1.1 p. 141 s). Elle ne revêt aucune autorité de chose jugée (sauf pour la poursuite en cours et à l'égard des pièces produites) (ANDRÉ SCHMIDT, Commentaire romand, Poursuite et faillite, 2005, n° 5 ad art. 79 LP); elle n'a même pas autorité de chose jugée dans le cas où le créancier introduit une nouvelle poursuite (<ref-ruling> consid. 3 p. 50 s). Ainsi, la décision sur la demande de mainlevée n'a pas autorité de chose jugée dans un procès ultérieur sur le fond, notamment une action en reconnaissance de dette ou en libération de dette (FABIENNE HOHL, Procédure civile I, Berne 2001, n° 1320 p. 248).
Ainsi, le premier grief est dépourvu de tout fondement. Peu importe que l'arrêt attaqué soit ou non conforme au dispositif ou aux considérants du jugement de mainlevée, puisque celui-ci n'a aucune autorité de chose jugée dans la procédure sur le fond.
2.2 Comme second grief, le recourant soutient que la cour cantonale a déterminé arbitrairement la volonté réelle des parties (cf. art. 97 al. 1 et 105 al. 2 LTF; art. 9 Cst).
La cour cantonale a constaté que les parties sont convenues que le locataire pouvait mettre fin au bail de façon anticipée s'il perdait le mandat dont il tirait l'essentiel de ses ressources; elle a également observé que les parties n'avaient pas réglé les modalités d'exercice de ce droit, notamment quant à des délais ou un terme. Sur ces points, il n'y a pas de contestation entre les parties et on ne voit pas en quoi pourrait consister l'établissement arbitraire des faits.
Le second grief est donc sans objet.
2.3 Constatant que les parties n'avaient pas réglé les modalités d'exercice du droit, la cour cantonale s'est demandée, en procédant à une interprétation ou un complètement du contrat, comment devait s'exercer la faculté de résilier le bail de manière anticipée.
L'interprétation d'un contrat selon le principe de la confiance (<ref-ruling> consid. 3.3 p. 681 s.), de même que son complètement (<ref-ruling> consid. 4b p. 488), sont des questions de droit que le Tribunal fédéral, saisi d'un recours en matière civile, peut revoir librement (art. 106 al. 1 LTF).
En acceptant la clause ajoutée par le locataire, les parties ont manifestement admis que si ce dernier perdait le mandat qui constituait l'essentiel de son activité et dont il tirait l'essentiel de ses ressources, les bases nécessaires du bail seraient modifiées pour lui et qu'on ne pouvait exiger qu'il poursuive le contrat dans ces conditions. Les parties ont donc admis par avance, pour couper court à toute discussion, que la perte de ce mandat constituerait un juste motif de résiliation anticipée au sens de l'art. 266g CO (cf. <ref-ruling>). Elles ont ainsi créé conventionnellement un juste motif de résiliation anticipée. En adoptant cette clause, elles se sont interdites de contester que la perte du mandat constitue un juste motif de résiliation anticipée. Il n'empêche que les motifs qui ont conduit à l'acceptation de cette clause montrent que les parties avaient à l'esprit la figure juridique du juste motif qui empêche de poursuivre un contrat de durée jusqu'à son terme. Dans la mesure où les parties n'ont pas réglé plus précisément les modalités de la résiliation anticipée, il est logique et conforme aux principes d'interprétation d'appliquer aux questions non résolues les règles générales relatives à la résiliation anticipée pour justes motifs.
Il faut ensuite observer que la clause ajoutée par le locataire (et acceptée par la bailleresse) donnait à celui-ci la faculté de résilier le bail de façon anticipée, mais ne lui en faisait pas l'obligation. Le locataire restait libre de résilier ou non le contrat de façon anticipée et il lui était loisible, notamment s'il avait développé d'autres affaires, de poursuivre le bail nonobstant la fin du mandat cité. La clause ajoutée devait seulement lui permettre de résilier le bail de façon anticipée si la fin du mandat lui rendait insupportable la continuation du bail jusqu'à son échéance ordinaire.
La doctrine en a donc déduit, dans les cas de justes motifs au sens de l'art. 266g CO, que la partie doit résilier immédiatement après la survenance du juste motif, faute de quoi elle montre par son attitude que celui-ci ne lui rend pas insupportable la continuation du contrat (PETER HIGI, Zürcher Kommentar, 4e éd. 1995, n° 59 ad art. 266g CO; ROGER WEBER, Basler Kommentar, 4e éd. 2007, n° 6 ad art. 266g CO; MARIE-NOËLLE VENTURI-ZEN-RUFFINEN, La résiliation pour justes motifs des contrats de durée, thèse Fribourg 2007, no 118 p. 310). La jurisprudence a d'ailleurs développé des règles très strictes à ce sujet dans le cas plus ou moins analogue de la résiliation d'un contrat de travail pour justes motifs (<ref-ruling> consid. 4.4 p. 34 et les arrêts cités). En décidant, en l'absence de convention spéciale, d'appliquer ces principes généraux au juste motif convenu par les parties, on ne voit pas que la cour cantonale ait violé le droit fédéral.
Elle a constaté en fait - d'une manière qui lie le Tribunal fédéral (art. 105 al. 1 LTF) - que le locataire a été informé, à la fin du mois de mars 2003, que le mandat prendrait fin dès le début du mois de juillet 2003; il n'a toutefois résilié le bail que par courrier du 30 octobre 2003, soit sept mois après avoir eu connaissance du juste motif et quatre mois après avoir commencé à en subir les effets. En différant dans une telle mesure la résiliation, le locataire a montré que, subjectivement, la fin du mandat ne lui rendait pas insupportable la continuation du bail. En admettant qu'une résiliation tardive n'est pas conforme au sens et au but d'une clause instituant un juste motif de résiliation anticipée et que le congé devait donc être considéré comme inefficace, la cour cantonale n'a violé aucune règle du droit fédéral.
Le recourant tente de soutenir qu'il espérait obtenir un autre mandat, mais il ne ressort pas de l'état de fait déterminant (art. 105 al. 1 LTF) qu'il ait fait la moindre démarche dans ce sens, ni qu'il en ait informé son cocontractant. Il n'y a donc pas à examiner la question sous cet angle, puisque l'analyse de la cause doit se fonder exclusivement sur l'état de fait arrêté souverainement par la cour cantonale.
3. Il résulte des considérants qui précèdent que le recours doit être rejeté.
Les frais judiciaires et les dépens sont mis à la charge de la partie 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 à la Chambre d'appel en matière de baux et loyers du canton de Genève.
Lausanne, le 9 juin 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Le Greffier:
Klett Piaget