You really aren't giving enough information for anyone to make a good guess as to what could be going wrong. Mail routing problems can be complex, anything from a misconfigured hostname, DNS resolution problems, spam filter, etc.

A couple of questions:

What do you mean with or without headers?
How are you trying to debug this? What shows up in the logs?

Here's a tip:

apt-get install postfix webmin-postfix

Now go to the webmin web interface and see if you can configure the myhostname parameter.