Lost Messages in Exchange 5.5

We have been having sporadic problems with email messages being lost. More specifically, a couple of users in Hong Kong and Singapore have sent messages to a couple of our users around 3am our time and the messages did not arrive here, but the other users on their domain received the message. We can send email back and forth on a regular basis, but occasionally messages they send overnight do not get here. Had their tech check the local addresses and global addresses to verify they are correct and they are. Our backups occur at around 9pm Central Time….can’t figure out what may be causing this…