Sending email from your app directly to a user (ie, connecting to their smtp server) is always going to be a bottleneck. Your best bet is to set up a sendmail (or postfix) server of your own and queue the email into that.

By off-loading the mail delivery to a sendmail/postfix server, you free your app from the normal email blocking situations (dns lookups/timeouts, address verification, retries, etc). You can also tweak the server to send email how you want (right away, every X minutes, retry X number of times, etc).