Outlook behaviour following sp4 install

[PaulBarron]

SP4 has just been installed on my exch 5.5 server. Following this, all Outlook 97 clients that are configured to display a notification message when new mail arrives get the following error when clicking on yes to view the new mail;

The Item has been moved or Deleted

If you click on OK, then go into the inbox, you can see and indeed open the new email.

Any ideas why this may be happening and how to correct it. It can't be storage limits as none of the mailboxes in question are anywhere near their limit

 

[PaulBarron]

My mistake. It was NT sp6 we installed that caused the problems we are now having.

Any advice?