Hosting EMail And Web In Different Servers

I'm experiencing some issues that I thought were something normal, or something that you could expect when working like this, but I think that it is something that should NOT happen.

We own a dedicated server, where we host some sites we develop (around 80 right now). We usually host both email and web page in the same server, but recently we had two customers who wanted to host email in a different place. The first one has its own server with proxy, and the second one is waiting the previous company to change DNS values.

The problem shows when we try to send an email from ANY domain hosted in our server, to one of these domains. From Outlook, the error is something like "no such user found", but the REAL problem comes when a PHP script (usually a contact form) tries to send the email. This mails get simply lost, and the customer never receives them.

My question is: What do I configure, or how do I do so my webserver looks for the real DNS, instead of trying to send the mail directly to the local domain?