Have you been able to look at any of the error logs to see what is happening. The SMTP protocol specifies number of handshaking steps that describe the process of sending the messages.
Basically, your smtp server will connect to the next SMTP server. This can either be the receiving server or the next hop along the path. When this happens, a HELO process will occur, possibly with an authentication step and then the sending message will say that it has "mail to" a specific user. At this point, if the recipient is deemed valid, the receiving SMTP server should give the go ahead for the message transmission.
Given that outgoing messages are transmitted, it sounds like there is an issue when the (receiving) SMTP server recognizes the recipient as being one of its own. What you will need to figure out is on these cases whether the messages are being accepted and not delivered or if they are being rejected. It could be that the messages are getting accepted, but the local delivery is incorrect.