mail server problems?

Hi there,

I recently purchased a VPS to host some of my websites. The host configured the VPS for me, and all was going great for about a week. However, in the last 24 hours, mail has stopped working. When I send an email from an external email address to one of my email addresses setup on the VPS, I get this message:

Quote:

This is an automatically generated Delivery Status Notification

Delivery to the following recipient failed permanently:

recipient-email-address@internal-domain.com

Technical details of permanent failure:
PERM_FAILURE: SMTP Error (state 9): 550-Verification failed for <sender-email-address@external-domain.com>
550-unrouteable mail domain "external-domain.com"
550 Sender verify failed

----- Original message -----

Received: by 10.70.68.2 with SMTP id q2mr23032wxa;
Fri, 26 May 2006 19:13:49 -0700 (PDT)
Received: by 10.70.57.2 with HTTP; Fri, 26 May 2006 19:13:49 -0700 (PDT)
Message-ID: <63d98d010605261913w2095f47ctd0f89bdb1a43e995@mail .external-domain.com>
Date: Sat, 27 May 2006 12:13:49 +1000
From: "Name of sender" <sender-email-address@external-domain.com>
To: "Name of recipient" <recipient-email-address@internal-domain.com>
Subject: test
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----=_Part_137_14517455.1148696029633"

------=_Part_137_14517455.1148696029633
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

test

------=_Part_137_14517455.1148696029633
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

----- Message truncated -----

Of course I've changed the email addresses, but you can see the messgae I get.

I've tried restarting exim, and the pop3 service, but still have this problem. When I check the service status within cpanel, everything is showing as running fine.

Can somebody help? I have users calling me every 5 seconds complaining about not getting/be able to send mail.

Thanks,
Tim.