I have the exact same problem, though running exchange 2000 etc... I have a case open with TAC and they are not yet able to resolve it. Reboots fix the problem for a short period of time. Also, internal forwardin of msgs to other internal fails as well. Messages are nowhere to be found.