Multiple issues: search tool hangs on client, services won't stop on server

I apolgize in advance that this is a long post, but I think that the more detail the better.

Here goes: We were working on short-cutting several stores of mailboxes over the course of a week. At the end of the week, it was noticed that archiving of any mail had abruptly stopped. It was also noticed under Message Queuing that ex_incoming_queues_0, 1, 2 and 3 (Message_Marshaller_0, 1,2 3) were filling up with messages and that nothing was going to the archive. The LEGATO services were stopped and the server was rebooted. exQuery.exe and exEmail.exe had to be stopped from the task manager as they had timed out with the message ¿the service could not be stopped in a timely manner.¿

After rebooting, the queues eventually emptied and archiving re-commenced.

In the two weeks since then, we have had numerous issues with the search tool and continue with the issues with the services on EmailXtender.

1. We are unable to launch the search tool on demand from Outlook 2003. The search tool will hang when opened. Sometimes it will say ¿Authenticating User Privileges¿ but never complete that action; other times nothing will happen. If the services on the EmailXtender server are restarted, then the search tool immediately works. If we try to use it again in about two hours, it no longer works.

2. If trying to restart LEGATO services on EmailXtender server, first the server is unable to stop exQuery.exe (EmailXtender Query). That service has to be forcibly stopped using the task manager (stop process). If that service does stop properly or is forcibly stopped, the next service that is problematic is EmailXtender Data Source (exEMail.exe). Then the services are all able to be restarted properly.

This happens several times per day (or as often as we restart the services). The event log is filled with the following events:

Event Type: Information
Event Source: EmailXtender
Event Category: AddrRule
Event ID: 0
Date: 5/30/2008
Time: 2:18:47 PM
User: N/A
Computer: W3EXTEND
Description:
CoExAddrRule::ShouldArchiveMsg - Waiting for Policy lock to free.
Total Timeouts: 5

Event Type: Information
Event Source: EmailXtender
Event Category: AddrRule
Event ID: 0
Date: 5/30/2008
Time: 2:19:13 PM
User: N/A
Computer: W3EXTEND
Description:
CoExAddrRule::EnsurePolicyEngine - Waiting for Policy lock to free.
Total Timeouts: 5

These events are marked informational and repeat over and over, incrementing by 5 (so next time total timeouts are 10) until the services are stopped. The next time the events start the timeouts start at 0 again. The first time we saw these messages was when the ex_incoming_queues were backing up. They occur periodically after that ¿ if the search tool isn¿t working, chances are these events will occur on the server at the same time.

Before this we have had periodic issues with archiving stopping, but each time we could find a definite cause that could be fixed fairly easily, like a message that couldn¿t be processed. Once that message was removed everything worked again. This time, we are at a loss for what is going on!

Our environment:

Windows 2003 R2 SP2
EmailXtender 4.81.563; using journaling to capture mail.
Exchange 2003 SP2 on Windows 2003 SP2- Front End with Back End Cluster
SQL Server 2005 SP2 (installed SP2 after the above started in hopes of fixing it)
DiskXtender 6.2.090
Centerra

Can anyone point me in the right direction or offer any suggestions of where to start?