I have Exchange 2003, users have outlook 2000

I have one user that when they select the INBOX in outlook, then click on
TOOLS, the 'recover deleted Items' is grayed out. Yet when they click on
other folder, it is not grayed out.
If that users outlook is opened on another machine, and they click on INBOX,
the 'recover deleted items' option is available.

Any ideas?