Search returns old messages only

[Les]

When I do a search in MS Outlook 2003 using Advanced Find and specifying
somebody's name in the From field, the most recent result is several months
ago. This is happening in other users Outlook as well. I received an email
from the said person today as well as several others from this same person
over the past few weeks but they are not revealed in the results of the
search.
Please help!!!
TIA!

 

[Les]

I forgot to mention that we are using Exchange 2000 on a 2000 Server.