I have just had to fix a debian5 system which suddenly started rejecting correctly addressed emails as '550 relay not permitted.' It turned out that rogue exim4 config files had been injected into the system at /etc/exim4/exim4.conf and /etc/exim4/exim.conf and these were messing up mail routing.
The system had been compromised similar to this description: Details of the root kit that got installed on my Debian Lenny boxes due to the exim remote root exploit : netsec
I also found a few strange processes running which were started around the same time as the problem started. Note that you must restore a valid version of ps (see the link) before you use it to look for rogue processes.
The security patch is described here: [SECURITY] [DSA-2131-1] New exim4 packages fix remote code execution
I strongly recommed that you apply this patch if it applies to you.