Issue with php's mail again

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.

I've changed to postfix to see if it works... same crap. vBulletin manages to send emails. But a simple <?php mail("tome@mydomain", "test", "test email"); ?> doesn't work. I've tried with and without headers. The headers include all the same headers as vBulletin does! Your change made no difference.

sendmail_path =/usr/sbin/sendmail -t -i -f mailer@yourdomain.com