On my linode I server up web pages for a bunch of random domains.

I have two IPs one for maindomain.com only and the other for domain1.com, domain2.com,etc.

Right now I'm using sendmail and it gives me a bunch of errors like this when it tries to send mail to various domains.

Feb 29 12:00:07 scylla sm-mta[3526]: STARTTLS=client, relay=aspmx.l.google.com., version=TLSv1/SSLv3, verify=FAIL, cipher=RC4-SHA, bits=128/128
Feb 29 12:08:00 scylla sm-mta[3788]: STARTTLS=client, relay=gmail-smtp-in.l.google.com., version=TLSv1/SSLv3, verify=FAIL, cipher=RC4-SHA, bits=128/128

Since I have a valid SSL cert for maindomain.com I'd like to set it up as the smart host using this guide: http://library.linode.com/email/exim/send-only-mta-ubuntu-10.04-lucid but my question is how would I setup the hostname for it?

Should the hostname resolve to server.maindomain.com?
Does my IP setup complicate things at all?

I might be wrong here, but I think I recall something about tls-verifies going awry when using anonymous connections. It's not totally uncommon for SMTP-servers to use this, as it is cheaper, in the form of consumed resources, and you more or less just want the encryption. In other words, try something different than google, and see what you get for resultes.

You can try something like this to verify that the certificate you are exposing actually validates as expected

$ openssl s_client -connect localhost:25 -starttls smtp -CApath /etc/ssl/certs

This should output a bunch of info..

[...]
New, TLSv1/SSLv3, Cipher is DHE-RSA-AES256-SHA
Server public key is 2048 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : TLSv1
    Cipher    : DHE-RSA-AES256-SHA
    Session-ID: 1195CCEBCFF2538BF873529BD12023ACB021A5EBBAC8AF09EEAB236AB1BBE732
    Session-ID-ctx:
    Master-Key: 8A547A5E9653806B31EA8982E22184D9E0DFF40EB8A3E6D7AFA1848F9A6D359C0ADF0FD8392C8391DCA3F47D881C474C
    Key-Arg   : None
    Start Time: 1330556960
    Timeout   : 300 (sec)
    Verify return code: 0 (ok)
---
250 DSN
QUIT
DONE

..but what is interesting here is the bottom part, Verify return code: 0 (ok)

This tells us that the chain is correctly set up for out externally exposed SMTP-server.

Here are the two responses I think might give the most information.I don't mind a bit of overhead to send all emails over SSL and would like to do that if at all possible. It may end up being that I didn't get SSL working on sendmail when I first set it up so don't count that out of the equation.

openssl s_client -connect localhost:25 -starttls smtp -CApath /etc/ssl/certs/
CONNECTED(00000003)
didn't found starttls in server response, try anyway...
8672:error:140770FC:SSL routines:SSL23_GET_SERVER_HELLO:unknown protocol:s23_clnt.c:601:

openssl s_client -connect aspmx.l.google.com:25 -starttls smtp -CApath /etc/ssl/certs/
CONNECTED(00000003)
depth=2 /C=US/O=Equifax/OU=Equifax Secure Certificate Authority
verify return:1
depth=1 /C=US/O=Google Inc/CN=Google Internet Authority
verify return:1
depth=0 /C=US/ST=California/L=Mountain View/O=Google Inc/CN=mx.google.com
verify return:1
---
Certificate chain
 0 s:/C=US/ST=California/L=Mountain View/O=Google Inc/CN=mx.google.com
   i:/C=US/O=Google Inc/CN=Google Internet Authority
 1 s:/C=US/O=Google Inc/CN=Google Internet Authority
   i:/C=US/O=Equifax/OU=Equifax Secure Certificate Authority
---
Server certificate
-----BEGIN CERTIFICATE-----
MIIDWjCCAsOgAwIBAgIKFeZKUwADAAA7OTANBgkqhkiG9w0BAQUFADBGMQswCQYD
VQQGEwJVUzETMBEGA1UEChMKR29vZ2xlIEluYzEiMCAGA1UEAxMZR29vZ2xlIElu
dGVybmV0IEF1dGhvcml0eTAeFw0xMTExMTgwMTU5NDFaFw0xMjExMTgwMjA5NDFa
MGcxCzAJBgNVBAYTAlVTMRMwEQYDVQQIEwpDYWxpZm9ybmlhMRYwFAYDVQQHEw1N
b3VudGFpbiBWaWV3MRMwEQYDVQQKEwpHb29nbGUgSW5jMRYwFAYDVQQDEw1teC5n
b29nbGUuY29tMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDI4N/B9MTCltGh
3De61YB1MWaQd+aaluLfDmRmT4Jt1YLaovSBwXbxzQqqJaFhVNa1O0ZCG7VCQQEn
TwWEIGiFQBpnI3S7E3pd0O4WAt1PRyiRVNwbR9a8KFSSMkEdEn/z7+Tg/jjoS47P
N+WUmqeDKNSxYOX2Qq0u/BQjiUHYfQIDAQABo4IBLDCCASgwHQYDVR0OBBYEFONB
VW/z/RjhVc4wlx/JPnQKpLGFMB8GA1UdIwQYMBaAFL/AMOv1QxE+Z7qekfv8atrj
axIkMFsGA1UdHwRUMFIwUKBOoEyGSmh0dHA6Ly93d3cuZ3N0YXRpYy5jb20vR29v
Z2xlSW50ZXJuZXRBdXRob3JpdHkvR29vZ2xlSW50ZXJuZXRBdXRob3JpdHkuY3Js
MGYGCCsGAQUFBwEBBFowWDBWBggrBgEFBQcwAoZKaHR0cDovL3d3dy5nc3RhdGlj
LmNvbS9Hb29nbGVJbnRlcm5ldEF1dGhvcml0eS9Hb29nbGVJbnRlcm5ldEF1dGhv
cml0eS5jcnQwIQYJKwYBBAGCNxQCBBQeEgBXAGUAYgBTAGUAcgB2AGUAcjANBgkq
hkiG9w0BAQUFAAOBgQC37YsqaD5aoQIjoS699o/ZE9G68LQsMvl++Cz0ZrGveGQt
MVDzdx6YkWF4h6R9p1LhccmYpROgQ0/BxDsUgHbW+hItk7iOIBW2KJ7BL3niFFiR
bGiDp3Q4E/8V2iHYmNjL7t9nF+z8ahhd0GrUCfDZ8S9v3iXm0F1cohTaGGh8Mw==
-----END CERTIFICATE-----
subject=/C=US/ST=California/L=Mountain View/O=Google Inc/CN=mx.google.com
issuer=/C=US/O=Google Inc/CN=Google Internet Authority
---
No client certificate CA names sent
---
SSL handshake has read 1928 bytes and written 342 bytes
---
New, TLSv1/SSLv3, Cipher is RC4-SHA
Server public key is 1024 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : TLSv1
    Cipher    : RC4-SHA
    Session-ID: F6635C550B0634BB3267E9AC31A5711725EA3B8E065A1AB52ABD2E697B34316F
    Session-ID-ctx: 
    Master-Key: A2AFB354518CF30A9BF1A73A548CF232F0C0C8457F16E5223B0A39A0D2E260F3DBB0FCEAA774D813C0A1EED8CDA5BFF3
    Key-Arg   : None
    Start Time: 1330557435
    Timeout   : 300 (sec)
    Verify return code: 0 (ok)
---
250 PIPELINING
QUIT
DONE