Kan ikke søge i E-mails

Vi har det problem at flere af vore brugere ikke kan søge i deres mail-mapper!
Det er endnu ikke klart hvornår problemet opstod.

Jeg har 2 mails liggende i min indbakke, begge med ordene "Venlig hilsen" i. Når jeg indtaster ordene i boksen Søg efter og klikker på Søg nu, finder Outlook INGEN af de 2 mails!
(feltet Søg i er sat til Indbakke og der er hak ud for Indstillinger -> Søg i al tekst i alle meddelelser)

Hvis jeg klikker på Indstillinger -> Avanceret søgning og sætter
Søg efter ordet = Venlig hilsen
I = emnefeltet og meddelelsesteksten
og har KUN valgt at søge i mappen Indbakke (har 2 andre undermapper), så henter den 1 mail fra en af under mapperne og ikke mere og det på trods af at undermappen indeholder 1000 vis af mails (Kvitteringer) med samme tekst (Venlig hilsen)!

Hvad ER der dog galt?! :(