Debian – Exim rejects recipient address on the domain

I have a dedicated server (debian) on which I have installed Exim and Dovecot. Everything worked fine until around a month ago. I tried to reinstall and reconfigure exim but I keep having all the incoming emails rejected.

Outlook says:

A message that you sent could not be delivered to one or more of its recipients. This is a permanent error. The following address(es) failed:

technical@mydomain.com
SMTP error from remote mail server after RCPT TO::
host mail.mydomain.com [94.76.##.##]: 550 relay not permitted

GMAIL:

Delivery to the following recipient failed permanently:

technical@mydomain.com

Technical details of permanent failure:
Google tried to deliver your message, but it was rejected by the recipient domain. We recommend contacting the other email provider for further information about the cause of this error. The error that the other server returned was: 550 550 relay not permitted (state 14).

On the server side, my rejectlog file shows:

2011-01-04 17:09:21 H=mail-qw0-f53.google.com [209.85.216.53] F=<####@gmail.com> rejected RCPT : relay not permitted

… and the mainlog file:

2011-01-04 17:00:01 1PaAEr-0007vN-DX <= root@ETC_MAILNAME U=root P=local S=869
2011-01-04 17:00:01 1PaAEr-0007vN-DX ** root@etc_mailname: Unrouteable address
2011-01-04 17:00:01 1PaAEr-0007vY-Kn Error while reading message with no usable sender address (R=1PaAEr-0007vN-DX): at least one malformed recipient address: root@ETC_MAILNAME – malformed address: _MAILNAME may not follow root@ETC
2011-01-04 17:00:01 1PaAEr-0007vN-DX Process failed (1) when writing error message to root@ETC_MAILNAME (frozen)
2011-01-04 17:09:21 no IP address found for host MAIN_RELAY_NETS (during SMTP connection from mail-qw0-f53.google.com [209.85.216.53])
2011-01-04 17:09:21 H=mail-qw0-f53.google.com [209.85.216.53] F=<####@gmail.com> rejected RCPT : relay not permitted

then after the message becomes frozen:

2011-01-04 17:28:44 1PaAEr-0007vN-DX Message is frozen

Thank you for your help, any idea/comment is welcomed as I am really running out of idea to fix this issue,
Nicolas.

Oh and the PHP mail() function does not do anything as well, would it be linked to? I think mail() uses sendmail from my php.ini.