What kind of delete is being performed? A soft delete or a hard delete?
hard delete = SHIFT+ Delete or a move to a PST
soft delete = just the delete key
Hard deletes won't reconcile to a HH prior to 4.1 SP2 (but this function isn't even enabled by default so you'd need to enable it too)
I say get upgraded to 4.1 (SP4 is current as of now ... SP5 is due out Nov 28th), enable hard delete support, and go from there.
Anyhoo, support for 4.0 goes away come Feb. 1, 2008.
How to enable hard deletes