e-mail's sit in the queue for remote delivery for only one domain. All other addresses receive our e-mails

Are you able to ping the remote domain okay?  try pinging ping mail.remotedomain.com

I would try sending an email using a telnet session from your email server.   Open a command prompt and then do the following:

telnet <remote-domain> 25
Helo <your-domain>
mail from:<your email address>
rcpt to:<email addy at their domain>
data
<type msg here>..
.   (period indicates you are done typing the message)
quit  
Take note of any errors that are displayed and post them.   If you are unable to establish the initial telnet session, I would contact them and ask them whats up.

Thanks for a quick response.
No, I can not ping the reomte domain.

If the company has ICMP turned off on their firewall.....the system wouldn't reply to a ping.  

Response to txhockey26
Could not open a connection to the host, on port 25: Connection failed

it's most likely on their side if you can't send to one particular domain but others.  you may want to contact them to see what's going on.  


If you did the telnet test and still can't get in there, it's time to contact them or verify that the email address you're entering is correct.

That's true, it's possible they are not responding the the ping, but it's more likely that either,
1.  Thier mail server is down, or domain does not exist.
2.  There is a problem with your DNS, in communicating with thier domain.

If telnet does not work above, I would verifiy the domain is valid before spending anymore time.  If it is valid, and you still cannot ping, telnet, time to troubleshoot your DNS.

just to be on the safe side, can you verify if you're on any blacklists by going to www.mxtoolbox.com.

Ok.....just to make sure....go to a command prompt and type:  nslookup
This will take you to another prompt.   Type the following:
set type=mx
type domain name

This will return what is being used for mail.    Just in case that  mail.domain.com is not the correct alias and such.    Then type quit.    And go through the telnet session w/ the info that was returned from nslookup.    If the mx is the same as what you used initially, I would call the company.

Ok Firstly, this is what i get from nslookup

C:\Documents and Settings\administrator.WSTEAM>nslookup
Default Server:  dctsrv001.wsteam.com
Address:  172.19.2.1

> set type=mx
> homeoffice.gsi.gov.uk
Server:  dctsrv001.wsteam.com
Address:  172.19.2.1

Non-authoritative answer:
homeoffice.gsi.gov.uk   MX preference = 10, mail exchanger = clust
labs.com
homeoffice.gsi.gov.uk   MX preference = 20, mail exchanger = clust
elabs.com

cluster.gsi.messagelabs.com     internet address = 193.109.254.83
cluster.gsi.messagelabs.com     internet address = 194.106.220.3
cluster.gsi.messagelabs.com     internet address = 62.231.131.115
cluster.gsi2.messagelabs.com    internet address = 62.231.131.115

Secondly, Using www.mxtoolbox.com I am not on any Blacklist (Cool Tool by the way)

Thirdly, The e-mail addresses we are trying to send to definatley exist.

Thanks

Go through the telnet session using the     cluster.gsi.messagelabs.com  
I'm able to connect to that server from here.   Make sure you do this from your email server.   Being that I don't have an email address that is valid I can't go through the process....but that would look a little odd.   hehe    

And just as an fyi - the company you are trying to send email to is using message labs for antispam filtering.   So it's possible there is a bad setting there to.    But I think it's safe to say your next step will be contacting someone in IT on that end and explain what is taking place.    

I can only seem to get this far.

220 server-9.tower-185.messagel
helo wsteam.co.uk
250 server-9.tower-185.messagel
mail from: glen.moore@wsteam.co.uk
250 OK
rpct to: glen.moore@homeoffice.gsi.gov.uk
502 unimplemented (#5.5.1)

I'm going to say that I believe it's their side.


I did a telnet test on their server from my end and in order for it to respond to an ehlo/helo command, i had to specify my domain after that command.  That's not normal.  Alot of times it could be a rule in their spam filter and so forth.  I would contact them to get this resolved.


Because once I specified my domain, I was able to send a message.  

>>i had to specify my domain after that command.  That's not normal.

Since when?  That is quite normal, infact, the RFCs mandate that you need to specific a domain.  That Exchange doesn't enforce it, does not mean that those who do are in breach.

The best test of something like this is a third party;

http://www.zmailer.org/mxverify.html

Put the recipient email address in there and see if it goes.  As I have already done it, I can tell you that it works.  If it still doesn't work from your server, then it is more likely to not be a problem with their server;

Testing server at address: IPv4 62.231.131.115
[ CONNECTED! ]

 220 server-9.tower-185.messagelabs.com ESMTP
 EHLO z2.cat.iki.fi
 250-server-9.tower-185.messagelabs.com
 250-PIPELINING
 250 8BITMIME

Excellent! It speaks ESMTP!

 MAIL FROM:<>
 250 OK

Fine, it accepts NULL return-path as is mandated by RFC 2821 section 6.1

 RSET
 250 flushed
 MAIL FROM:<postmaster@z2.cat.iki.fi>
 250 OK
 RCPT TO:<glen.moore@homeoffice.gsi.gov.uk>
 250 OK
 RCPT TO:<postmaster@homeoffice.gsi.gov.uk>
 250 OK

Thanks for your help