If I instruct openssl s_client to use TLS1 for starttls, then the connection succeeds:
-bash-3.2$ openssl s_client -starttls smtp -crlf -tls1 -connect smialcott.com:25
CONNECTED(00000003)
depth=3 /C=SE/O=AddTrust AB/OU=AddTrust External TTP Network/CN=AddTrust External CA Root
verify return:1
depth=2 /C=GB/ST=Greater Manchester/L=Salford/O=COMODO CA Limited/CN=COMODO RSA Certification Authority
verify return:1
...
If I tcpdump sniff the connection, I can see that the failing connection uses an SSLv2 packet to contain the "Client Hello", whereas with -tls1 the "Client Hello" is contained in a TLSv1 packet. So the symptoms are consistent with SSLv2 connections don't succeed where TLSv1 connections do. Which is exactly what you want to be happening I believe.
However, I think the risk of Poodle to you is low, and you are quite inconvenienced by not receiving email from united airlines. So I would 1) complain to United Airlines, and 2) re-enable SSLv2. Or, if you can work out how to do it, create an exception for United's mail server IP addresses.