Try connecting directly to the SMTP port on the server via telnet? See the Wikipedia page for an illustrative example. Start with the following (for a SMTP connection at port to smtp.gmail.com at port 25). Replace with the server and port you are using. In the following, EHLO and HELP are typed at the client prompt, as part of the SMTP negotiation. Note that the server response TO HELP is to point you to a copy of the Simple Mail Transfer Protocol (SMTP).
$ telnet smtp.gmail.com 25
Trying 74.125.53.109...
Connected to gmail-smtp-msa.l.google.com.
Escape character is '^]'.
220 mx.google.com ESMTP k9sm2692779pbc.22
EHLO
250-mx.google.com at your service, [59.183.41.125]
250-SIZE 35882577
250-8BITMIME
250-STARTTLS
250 ENHANCEDSTATUSCODES
HELP
214 2.0.0 http://www.google.com/search?btnI&q=RFC+2821 k9sm2692779pbc.22
If you can get this far, I suspect you don't have connection issues. Just one question to clarify. Is Alpine trying to deliver your mail directly, or are you handing off the mail delivery to a local mail server eg. Exim or Postfix? I have all my mail handed off to Exim, and then Exim sends it to a smarthost, which seems the preferred thing to do for hosts that don't have a static IP address at least. One advantage of the latter approach is that you can look at your mail server logs and/or queue to see what is happening with your mail.