VPS Mail server help?

Hi,

Please forgive me for my lack on knowledge with linux etc. I have been using Plesk on a VPS which simplifies my server admin skills.

Over the past few months I have been having some email issues with my VPS.

I think this may be a DNS / MX record issue because I made some MX record changes a few months ago however this could be coincidence and I would be grateful for some guidance.

My VPS is hosted with 1&1 and on I host 2 domains on on this server:
FirstStopDigital.com (for the past year)
pb-net.co.uk (just added a few months ago).

My domain pb-net.co.uk was hosted by another firm and I recently moved it across to my VPS.

I use google mail servers for hosting my email which on my old host I modifed my DNS so that my mail would be directed to the gmail servers and all was fine.

pb-net.co.uk is now held with 123-reg.com and I set the DNS to point to my server (firststopdigital.com).

On my server under my pb-net.co.uk domain I created the MX records as suggested by google. Again, everything is good and works fine.

However, mail being sent from my firststopdigital.com domain has stopped / or a received a rejection email. I use the internal mail() php function to send mail on both my pb-net.co.uk and firststopdigital.com domains. It works fine on the pb-net.co.uk domain but not on the other!

I have re-started my qmail service and no difference.

This is the rejection email I get when I send a message:

===========================================
Hi. This is the qmail-send program at s15236419.onlinehome-server.info.
I'm afraid I wasn't able to deliver your message to the following addresses.
This is a permanent error; I've given up. Sorry it didn't work out.

<support@firststopdigital.com>:
Sorry. Although I'm listed as a best-preference MX or A for that host,
it isn't in my control/locals file, so I don't treat it as local. (#5.4.6)

===========================================

I read that adding my hostname to /var/qmail/control/locals file and the /var/qmail/control/rcpthosts may help.

/var/qmail/control/locals already contained localhost.
/var/qmail/control/rcpthosts was empty so into both I added firststopdigital.com

I tried again and this time a new rejection email was returned to me:

===========================================
Hi. This is the qmail-send program at s15236419.onlinehome-server.info.
I'm afraid I wasn't able to deliver your message to the following addresses.
This is a permanent error; I've given up. Sorry it didn't work out.

<support@firststopdigital.com>:
Sorry, no mailbox here by that name. (#5.1.1)
===========================================

I have run out of ideas now!

Can someone help me where to look or what to do next?

Thank you in advanced.

Paul