Actually, I think the problem lies on your server. When I did a NSLOOKUP on my DNS server for your domain, I get the following:
Non-authoritative answer:
greencell.co.uk MX preference = 40, mail exchanger = blackmail.nildram.co.uk
greencell.co.uk MX preference = 10, mail exchanger = mail.greencell.co.uk
greencell.co.uk MX preference = 20, mail exchanger = whitemail.nildram.co.uk
greencell.co.uk MX preference = 30, mail exchanger = mailq.nildram.co.uk
greencell.co.uk nameserver = dns01.techgate.co.uk
greencell.co.uk nameserver = dns02.techgate.co.uk
mail.greencell.co.uk internet address = 213.208.89.218
dns01.techgate.co.uk internet address = 217.161.12.176
dns02.techgate.co.uk internet address = 217.161.12.175
Then, when I did a DNS query on your server (at 213.208.89.218) I got the following:
> greencell.co.uk
Server: [213.208.89.218]
Address: 213.208.89.218
greencell.co.uk
primary name server = gc2kdar.greencell.co.uk
responsiblemail addr = admin
serial = 4921
refresh = 900 (15 mins)
retry = 600 (10 mins)
expire = 86400 (1 day)
default TTL = 900 (15 mins)
The important line here is the "primary name server", which points to gc2kdar.greencell.co.uk
And I think that that is the problem. You cannot resolve "gc2kdar.greencell.co.uk" with an IP address. If you try, you get a Host Does Not Exist error.
And if the primary name server for your domain can't be found, then how am I gonna resolve mail.greencell.co.uk?
So, I suggest you check at the gc2kdar.greencell.co.uk first. Contact your ISP (techgate.co.uk) and make sure they are ok. Then check out your own DNS and make sure it is ok. I think you will find theproblem at the ISP, personally!
Now, I am not the best at DNS (it is really complicated, IMHO), but this is what I am seeing.
hope this helps