I am not experiencing these issues. I have run through the same steps as gbruyn and when I have ActiveSync "connected" (i.e. Sync schedule set to "As items arrive") the changes replicate within 10 seconds. Regardless of which device (TP2 or Computer) first modifies the object (email, calendar event, contact, etc.) or which device deletes the object, the action\change always replicates to the other device within seconds. The only exception to this seems to be when I Delete a calendar appointment from Outlook on my Computer it is not removed from my TP2 until some other change occurs such as adding a new appointment from either the TP2 or Computer or manually initiation a Sync from the TP2 or receiving a new email, however, once that happens, the appointment is removed from my PT2.
What version of Exchange are you on?
I am currently on Exchange 2007 SP1 but did not have any of these issues when I was on Exchange 2003.