Faits:
A. Le 12 octobre 2002, X._ a acheté au Garage V._ à ... une voiture de marque xxx pour le prix de 50'800 francs. Il a conclu avec Y._ une assurance responsabilité civile et casco intégrale couvrant ce véhicule. Parmi les risques assurés figurent notamment le vol, qui est couvert sans franchise. En cas de sinistre, il est prévu une indemnisation correspondant à la valeur vénale majorée.
Le 10 novembre 2004, X._ a déposé plainte auprès de la police judiciaire de Divonne-les-Bains pour le vol de son véhicule survenu dans la nuit du 9 au 10 novembre 2004. Il a immédiatement annoncé le vol à l'assureur. Selon ses explications, il avait parqué la voiture le 9 novembre 2004 vers 20h00 dans la rue située devant son domicile et le lendemain, aux alentours de 6h30, il ne l'a plus retrouvée.
Par courrier du 11 novembre 2004, l'assureur l'a invité à fournir certaines pièces, en particulier toutes les clés du véhicule, ainsi qu'un avis de sinistre.
En date du 22 novembre 2004, X._ a rempli la déclaration de sinistre demandée, en indiquant qu'il avait reçu deux clés lors de la livraison du véhicule et que ces deux clés se trouvaient dans son appartement lors de la survenance du sinistre.
Interrogé par un inspecteur de sinistre le 29 décembre 2004, il a expliqué que l'une des clés était toujours sur lui ou sur la console à l'entrée de son appartement, tandis que l'autre restait dans son bureau à la maison. Il a affirmé qu'il n'avait jamais perdu de clé et n'avait pas commandé d'autre clé que les deux qu'il a reçues lors de la livraison.
Il a été établi que X._ avait commandé une autre clé pour la voiture au garage de ... le 18 novembre 2004 et qu'il l'a reçue le lendemain.
X._ a reconnu les faits et il a expliqué qu'il s'était rendu compte, au moment de restituer les deux clés à l'assurance avec sa déclaration de sinistre, qu'il en avait perdu une et qu'il a commandé une copie afin de ne pas avoir d'ennuis avec l'assurance. L'assureur a déposé plainte pénale contre X._ pour tentative d'escroquerie.
Il ressort du rapport de la police de sûreté que le garagiste A._ a paru quelque peu emprunté lorsqu'il a été interrogé au sujet de la copie de la clé; ce n'est que lors de son audition formelle qu'il a expliqué qu'il savait déjà lors de la commande de la clé que la voiture était volée.
Le véhicule de X._ a été retrouvé complètement calciné par l'unité de la gendarmerie nationale française du ... le 8 août 2005 à .... Il a été noté que X._ était originaire de cette région, qu'il y avait été élevé et y avait suivi une partie de sa scolarité, que sa famille y vit encore et qu'il s'y rend de temps en temps. Une plaque d'immatriculation volée le 30 novembre 2004 dans la même région a été retrouvée dans les abords immédiats du véhicule incendié. Un garagiste local a démonté la colonne de direction et a pu constater que celle-ci n'avait pas été forcée, ce qui impliquait que la personne qui avait mené le véhicule à l'endroit où elle a été incendiée disposait de la clé de contact.
Le 26 avril 2005, l'assureur a fait savoir à X._ qu'il refusait toute prestation pour le motif que celui-ci n'avait pas apporté la preuve, au moins sous la forme d'une haute vraisemblance, que son véhicule avait été volé.
Par ordonnance du 31 octobre 2005, le juge d'instruction vaudois a prononcé un non-lieu sur l'accusation de tentative d'escroquerie. Il a considéré que la réalité du vol était sujette à caution, mais que la preuve d'une tentative d'escroquerie n'était pas apportée.
Le 20 février 2006, le Procureur de la République du Tribunal de Grande Instance de Cusset a rendu un avis de classement sans suite en ce qui concerne la plainte relative au vol de la voiture.
B. Par demande du 4 décembre 2008 formée devant la juridiction vaudoise, X._ a conclu, avec dépens, à ce que la compagnie d'assurances soit condamnée à lui payer la somme de 41'265 fr. avec intérêt à 5 % l'an dès le 9 novembre 2004. Ce montant repose sur une évaluation faite par un expert mandaté par l'assureur le 9 novembre 2004.
Par jugement du 9 novembre 2009, le Tribunal civil de l'arrondissement de l'Est vaudois a condamné Y._ à payer à X._ la somme de 41'265 fr. avec intérêt à 5 % l'an dès le 1er juin 2007, statuant par ailleurs sur les frais et dépens.
Saisie par l'assureur, la Chambre des recours, statuant le 30 juin 2010, a annulé le jugement attaqué (sauf en ce qui concerne la taxation des frais) et a rejeté les conclusions du demandeur avec suite de frais et dépens.
C. X._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt du 30 juin 2010. Il conclut, sous suite de frais et dépens, à l'annulation de l'arrêt attaqué et à ce que l'on en revienne au jugement de première instance. L'intimée a conclu au rejet du recours dans la mesure de sa recevabilité 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 (<ref-law>) et dirigé contre un arrêt final (<ref-law>), rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire pécuniaire dont la valeur litigieuse atteint le seuil de 30'000 fr. (<ref-law>), le recours est en principe recevable, puisqu'il a été déposé dans le délai (art. 48 al. 1 et 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi.
L'intimée soutient que l'arrêt cantonal serait fondé sur une double motivation alternative, à savoir l'absence de preuve du sinistre d'une part et une prétention frauduleuse au sens de l'<ref-law> d'autre part. Le recourant n'invoquant - selon les titres contenus dans son mémoire - qu'une violation de l'<ref-law>, il n'aurait attaqué qu'une seule des deux motivations alternatives, ce qui devrait entraîner l'irrecevabilité du recours (cf. <ref-ruling> consid. 6.3 p. 120 s.).
Cette argumentation ne peut pas être suivie. La cour cantonale a observé, sous consid. 4, que l'assureur invoquait, d'une part, que la preuve du sinistre n'avait pas été apportée, et, d'autre part, qu'il y avait prétention frauduleuse au sens de l'<ref-law>. Elle a ensuite rappelé les principes juridiques concernant la preuve du sinistre (consid. 5a et b) et les principes régissant la prétention frauduleuse au sens de l'<ref-law> (consid. 5c). Au moment de trancher le cas (consid. 6), elle a admis que la preuve du sinistre n'était pas apportée et elle n'a pas pris position sur l'argument tiré d'une prétention frauduleuse. L'arrêt cantonal est donc fondé sur une seule motivation, à savoir l'absence de preuve du sinistre. Quant au recours déposé devant le Tribunal fédéral, il mélange un peu les deux moyens qui avaient été invoqués par l'assureur; dans les dernières pages où se concentre l'argumentation, on constate toutefois clairement qu'il critique l'arrêt cantonal en tant qu'il a admis que la preuve du sinistre n'était pas apportée. Le recourant attaque donc bien l'unique argument sur lequel l'arrêt cantonal est fondé. On ne saurait dire qu'il a laissé intacte une argumentation qui suffit à justifier la décision attaquée.
1.2 Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. En conséquence, il peut aussi être formé pour violation d'un droit constitutionnel (<ref-ruling> consid. 2.4 p. 313).
Le Tribunal fédéral applique le droit d'office (<ref-law>). 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.4 p. 400). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), 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.4 p. 400; <ref-ruling> consid. 2.2.1 p. 389).
Par exception à la règle selon laquelle il examine le droit d'office, il ne peut 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 (<ref-law>).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). 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. 2.4 p. 314; <ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401; <ref-ruling> consid. 8.1 p. 153) - ou en violation du droit au sens de l'<ref-law> (<ref-law>).
La partie recourante ne peut pas présenter un état de fait qui diverge de celui retenu par la cour cantonale, ni un fait qui n'est pas contenu dans son arrêt, sauf si elle démontre par une argumentation précise que l'on se trouve dans un cas où il est possible de s'écarter des constatations cantonales (<ref-ruling> consid. 1.2 p. 187; <ref-ruling> consid. 1.4 et 6.2). Une rectification de l'état de fait ne peut être demandée que si elle est de nature à influer sur le sort de la cause (<ref-law>). Le Tribunal fédéral peut cependant rectifier ou compléter même d'office les constatations cantonales lorsqu'elles sont manifestement inexactes (<ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de l'autorité précédente (<ref-law>).
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2. 2.1 La cour cantonale a rejeté la demande formée par le recourant en considérant que celui-ci n'avait pas prouvé, sous la forme d'une vraisemblance prépondérante, que son véhicule avait été volé. Le recourant le conteste.
2.2 Selon l'<ref-law>, le demandeur doit prouver les faits qui fondent sa prétention, tandis que sa partie adverse doit prouver les faits qui entraînent l'extinction ou la perte du droit (<ref-ruling> consid. 3.1 p. 323). Ces principes, qui sont également applicables dans le domaine du contrat d'assurance, impliquent qu'il incombe à l'ayant droit d'alléguer et de prouver notamment la survenance du sinistre assuré (<ref-ruling> consid. 3.1 p. 323; arrêt 5C.180/1997 du 8 septembre 1997 consid. 2b; arrêt 5C.240/1995 du 1er février 1996, consid. 2a).
Cette preuve étant par nature difficile à apporter, l'exigence de preuve est réduite et il suffit que l'ayant droit établisse une vraisemblance prépondérante (<ref-ruling> consid. 3.2 et 3.3 p. 325; arrêt 4A_180/2010 du 3 août 2010 consid. 2.4.1 et les arrêts cités), qui ne doit pas être confondue avec une simple vraisemblance (<ref-ruling> consid. 3.3 p. 325).
L'<ref-law> donne à l'assureur le droit à la contre-preuve et il peut donc apporter des éléments propres à créer un doute et à ébranler la vraisemblance que l'ayant droit s'efforce d'établir. Le juge doit procéder à une appréciation d'ensemble des éléments qui lui sont apportés et dire s'il retient qu'une vraisemblance prépondérante a été établie (<ref-ruling> consid. 3.4 p. 326 s.; arrêt 4A_180/2010 déjà cité consid. 2.4.1; arrêt 4A_186/2009 du 3 mars 2010 consid. 6.2.2 et 6.3).
Il n'apparaît pas que la cour cantonale ait méconnu ces principes, ni qu'elle ait mal interprété la notion contractuelle du sinistre assuré.
Il n'est pas contesté que le recourant a prouvé qu'il avait conclu un contrat d'assurance avec l'intimée et que ce contrat couvrait notamment le risque de vol. Il lui restait donc à prouver, outre la quotité du dommage, que son véhicule avait été volé. Une vraisemblance prépondérante est à cet égard suffisante.
Il n'apparaît pas que la cour cantonale se soit trompée sur le degré de preuve exigé. Il n'y a donc pas trace d'une violation du droit fédéral à cet égard.
Seule est litigieuse la question de savoir si elle a correctement apprécié les moyens de preuve réunis.
2.3 L'appréciation des preuves se rattache à l'établissement des faits; elle ne peut être revue qu'en cas d'arbitraire. L'appréciation des preuves n'est arbitraire que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, s'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée ou encore si, sur la base des éléments recueillis, il a fait des déductions insoutenables (<ref-ruling> consid. 2.1 p. 9).
En l'espèce, il est établi et non contesté que le recourant a déclaré à l'assureur qu'il n'avait reçu que deux clés de la voiture et qu'il n'en avait pas commandé d'autre. Cette affirmation était mensongère, puisqu'il a dû reconnaître, confronté à un moyen de preuve, qu'il avait en réalité commandé une copie de clé après la survenance prétendue du sinistre afin de pouvoir rendre deux clés à l'assurance. Dès lors qu'il est ainsi établi qu'il a disposé de trois clés (deux clés reçues à la livraison et une clé commandée après le sinistre prétendu) et qu'il n'en a rendu que deux à l'assurance, il faut constater que le sort de la troisième clé reste inconnu. Il n'est donc pas exclu que le recourant ait à cette époque conservé une clé ainsi que la voiture. Qu'il ait menti à l'assurance et qu'il ait procédé de manière à ce qu'il y ait une troisième clé dont le sort est inconnu sont des circonstances suspectes.
La voiture du recourant a été retrouvée sensiblement plus tard entièrement calcinée et il est logique de penser qu'elle a été brûlée en vue d'en empêcher l'identification. L'arrêt cantonal, se référant à l'ordonnance du juge d'instruction, indique que la voiture a été retrouvée dans une forêt en Auvergne. A l'alinéa suivant, la cour cantonale relève qu'elle a été retrouvée à ..., dans l'Ain. Ces constatations de fait sont contradictoires. Le recourant en a tiré argument, relevant que ses parents ne sont pas domiciliés dans l'Ain à proximité du lieu où la voiture a été retrouvée. Il y a donc une contradiction sur un fait pertinent et le Tribunal fédéral doit procéder à une rectification d'office, en application de l'<ref-law>, s'il dispose pour cela de preuves univoques et indiscutables. La cour cantonale et le recourant se sont manifestement fondés sur les rapports de la gendarmerie française, qui sont restés au dossier et dont l'authenticité ne peut sérieusement être mise en doute.
La lecture des deux procès-verbaux de gendarmerie produits par le recourant lui-même (pièces nos 10 et 17) révèlent des fait troublants, correspondant à ce que la cour cantonale a retenu de manière résumée. Le recourant est né à ..., dans l'Allier (région : Auvergne); la voiture calcinée a été découverte le 8 août 2005 près de ..., dans l'Allier (pièce n° 10). Selon un témoin, elle ne se trouvait pas à cet emplacement la veille, de sorte qu'on peut admettre qu'elle venait d'être brûlée (pièce 17); la plaque d'immatriculation trouvée à proximité correspond à une plaque volée dans la nuit du 30 novembre au 1er décembre 2004 à ..., dans l'Allier (pièce n° 17, deuxième rapport). Le lieu où la voiture a été retrouvée se trouve à quelques kilomètres (environ 17 km selon le site viamichelin) de la résidence familiale ..., dans l'Allier, où se trouvait X._ au moment où la voiture a été découverte (pièce n° 17, deuxième rapport). L'Allier étant sensiblement éloignée du lieu du vol (Divonne-les-Bains, dans l'Ain), seule une coïncidence extraordinaire pourrait expliquer qu'elle ait été brûlée dans l'Allier, à quelques kilomètres de l'endroit où résidait le recourant. A cela s'ajoute qu'un garagiste a affirmé que la colonne de direction n'avait pas été forcée, ce qui démontrerait que la voiture avait été amenée en utilisant la clé de contact.
Au vu de l'ensemble de ces éléments, la cour cantonale n'a pas apprécié les preuves de manière arbitraire en concluant que le recourant n'était pas parvenu à prouver, avec une vraisemblance prépondérante, qu'il avait été victime d'un vol de sa voiture. Peu importe ici qu'une tentative d'escroquerie n'ait pas été prouvée avec le niveau de certitude requis; la seule question pertinente est de savoir si le recourant, lui, a apporté la preuve, avec une vraisemblance prépondérante, que sa voiture lui a été volée.
Les arguments qu'il invoque sont impropres à rendre arbitraire la conclusion à laquelle est parvenue la cour cantonale. Le recourant fait valoir en particulier que sa situation financière est saine - ce qui n'est pas constaté par la cour cantonale (<ref-law>) - et qu'il n'avait pas de raison d'échafauder un vol fictif. Il ressort cependant de l'évaluation du véhicule, à laquelle il se réfère lui-même (pièce n° 13 de son bordereau) que la valeur actuelle du véhicule était de 20'900 fr. et que l'indemnisation selon le système de la valeur vénale majorée lui permettait de recevoir 41'265 francs. Il pouvait avoir de nombreuses raisons de préférer recevoir cette somme plutôt que de garder une voiture qui ne valait plus qu'environ 20'000 francs. Toute l'argumentation du recourant est impropre à ébranler la conclusion que l'existence de ce vol est douteuse, de sorte que le recourant n'a pas apporté la preuve qui lui incombait, ce qui justifie son déboutement.
3. Le recours doit donc être rejeté.
Les frais judiciaires et les dépens doivent être 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 participants à la procédure et à la Chambre des recours du Tribunal cantonal du canton de Vaud.
Lausanne, le 4 janvier 2011
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Le Greffier:
Klett Piaget