Hi,
I have seen somthing slightly like this before. I don't remember the exact solution but do remember it was something we got MS PSS involved in.
I would suggest you first run the Exchange Best Practise Analyser and see if that turns up anything obvious.
If not, I would suggest you give PSS a call.
Cheers
Nathan
Nathan Winters - MVP Exchange Server
MCSE & MCSA 2000 & 2003 + Messaging, MCITP Exchange 2007, MCP, VMWare VCP v2 & v3.
Welcome to the Microsoft Messaging and Mobility User Group: http://www.mmmug.co.uk