... deliver an encrypted email?
First, there is a difference between transferring encrypted mails and the use of STARTTLS you ask about. Encrypting mails refers usually to end-to-end encryption using PGP or S/MIME, i.e. the sender encrypts and the recipient decrypts the mail. STARTTLS instead is not end-to-end but only hop-by-hop encryption: each hop (mail server) on the way has access to the plain mail and only the transport between the hops is encrypted.
... upgrade the tcp connection to TLS, but am I really expected (as a server) to do that on remote port 25?
You are expected to use port 25 since this is the only port which is defined for delivery in connection with an MX record. The relevant standard for STARTTLS is RFC 3207. It describes a SMTP extension where the receiving mail server can announce support for STARTTLS inside the response to EHLO and the client (i.e. another mail server or a mail user agent) can then upgrade the current connection using the STARTTLS command. In short the flow is like this:
< 220 server.example.com SMTP ready
> EHLO client.example.org
> 250-8BITMIME
> 250 STARTTLS
> STARTTLS
< 220 go ahead
... TLS handshake happens, initiated by client ...
> EHLO client.example.com
< 250-8BITMIME
< 250 AUTH PLAIN LOGIN
...
... but I never saw in the logs any remote server trying to send STARTTLS
If you don't announce support for STARTTLS in the response to EHLO the client will not try STARTTLS.
... see that lock icon in Gmail, when I connect to google MX servers to send an email all I have to do is start a TLS session with STARTTLS on that port 25? Do I need a certificate validated by an authority just like SSL?
A certificate is only needed in case you are the mail server receiving mails and thus work as TLS server if STARTTLS is used. In case of sending mails to gmail you are the client sending mails. In this case you might use a client certificate but you don't need to. And since you are working with Perl: the current versions of Net::SMTP (starting with version 3.x) have support for TLS already included as long as IO::Socket::SSL is installed. You just need to add a call to starttls as documented to send mails with TLS.
