My server is reporting the Internal IP address in the RCPT TO command --

Here a log entry from a bounced mail:

NOQUEUE: reject: RCPT from host.domain.de[]: 450 4.1.1 <info@bad-address.de>: Recipient address rejected: unverified address: host mail.bad-address.de[] said: 451 temporary failure (#4.3.0) (in reply to RCPT TO command); from=<user@domain.de> to=<info@bad-address.de> proto=ESMTP helo=<host.domain.de>
I think that the recipient servers might be rejecting my mails because the internal IP is in there. ( I am not on any Blacklists.

This is a NATted server and yes, I have successfully implemented a split DNS setup.
I DO use a spam filter service from my ISP, so my MX is not the external IP address of the server, it is a different address.

How can I get the proper IP (external address) to show in the RCPT FROM command?
Does anyone have any other ideas as to why the failure above occurs, seemingly randomly, and only with a handful of recipients?