Exchange 2003 & TLS

Hi All

I'm trying to setup TLS for a specific domain and seem to have run into a couple of problems. I've installed a cert on the server (self signed not from a CA) when I connect via telnet I see:

250-TLS
250-STARTTLS

So I know it'll handle TLS (I think). I then created a SMTP Connector for the specific domain that I want to send TLS mail to and set the requires TLS in the Outboud securiy tab. On the receving computer I followed the same procedure, installed a cert (self signed once again) and tested the Virtual server. From what I can tell everything is setup properly.

When I send a message to that domain I can see the message in the ougoing queue sitting in a retry state, if I delete the message with an NDR I get the following message:

This message was rejected due to the current administrative policy by the destination server.  Please retry at a later time.  If that fails, contact your system administrator.

Am I missing something? Are there any other settings I need to look at? Since I'm going over the internet do I need to have certs that are signed by a trusted CA?

thanx for the help
Garry