J'avais réglé mon problème en allant dans mon dossier Outlook :
Disque C/Documents and settings/Votre nom/Application data/Identities/etc...
Et j'ai jetté alors le dossier des messages supprimé.
Outlook en a recréé un autre lors du redémarrage et ça a fonctionné à nouveau.
Bonne chance.