Our company is running an Exchange 2003 Standard (SP3) on W2003
server, serving about 300 users, all XP Pro using Outlook 2003 (SP3)
for mail client.

Recently (about 2 to 3 weeks), we started getting reports of a very
odd problem in Outlook related to search results:

Whenever, after using the search options in Outlook to locate some
mails, a user does something to one or more mails in the search
results that causes the mail to be moved from its original folder
(i.e. delete the mail or move it to a different folder), the search
results list isn't updated, so it looks like nothing happens. When the
user then tries the same operation again, or tries to open one of the
mails he tried to move (still from the search results), he gets a
"Client operation has failed" error.

However, when we close the search and run it again or browse through
the folders, the mails have been correctly moved/deleted/.... So what
seems to happen is that the operation (moving or deleting mails) does
work as intended (i.e. the mails are indeed moved or deleted), but the
search results pane simply doesn't get updated to reflect the changed
location of the mails, making it appear as if nothing happens. Since
what is shown in the results pane still points to the old location,
you get the "client operation" error when you try to do anything with
those mails (because they're simply not in the store at the location
the result points to).

We've been able to reproduce this problem on our test machines and
with different mailboxes, so it doesn't seem to be related to the
client. We've also tried it with a new mailbox, and the results are
the same. So we figure it's either a problem with our Exchange server
itself, or it must be related to some sort of update.