Instead of using the try/except's else block, you could simply return when it errors:

def send_message(addr, to, msg):
    ## Connect to host
    try:
        server = smtplib.SMTP(host) #can throw an exception
    except smtplib.socket.gaierror:
        return

    ## Login
    try:
        server.login(username, password)
    except SMTPAuthenticationError:
        pass # do some stuff here
    finally:
        server.quit()
        return False

    ## Send message
    try:
        server.sendmail(addr, [to], msg.as_string())
        return True
    except Exception: # try to avoid catching Exception unless you have too
        return False
    finally:
        server.quit()

That's perfectly readable and Pythonic..

Another way of doing this is, rather than worry about the specific implementation, decide how you want your code to look, for example..

sender = MyMailer("username", "password") # the except SocketError/AuthError could go here
try:
    sender.message("addr..", ["to.."], "message...")
except SocketError:
    print "Couldn't connect to server"
except AuthError:
    print "Invalid username and/or password!"
else:
    print "Message sent!"

Then write the code for the message() method, catching any errors you expect, and raising your own custom one, and handle that where it's relevant. Your class may look something like..

class ConnectionError(Exception): pass
class AuthError(Exception): pass
class SendError(Exception): pass

class MyMailer:
    def __init__(self, host, username, password):
        self.host = host
        self.username = username
        self.password = password

    def connect(self):
        try:
            self.server = smtp.SMTP(self.host)
        except smtplib.socket.gaierror:
            raise ConnectionError("Error connecting to %s" % (self.host))

    def auth(self):
        try:
            self.server.login(self.username, self.password)
        except SMTPAuthenticationError:
            raise AuthError("Invalid username (%s) and/or password" % (self.username))

    def message(self, addr, to, msg):
        try:
            server.sendmail(addr, [to], msg.as_string())
        except smtplib.something.senderror, errormsg:
            raise SendError("Couldn't send message: %s" % (errormsg))
        except smtp.socket.timeout:
            raise ConnectionError("Socket error while sending message")