If I had to bet, I'd bet that there's a lot of latency to your SMTP server. You say you're using google for SMTP, which I'm not familiar with, but that's going to be a far away server (relative to like, and SMTP box on your network). On top of that, you say you're running SMTP over SSL. SSL is a complex protocol with a lot handshaking before the connection is even established. This means the network latency between your server and the SMTP service is multiplied as the two machines do the SSL handshake dialog. Overall, it's not a great setup.
Some kind of work-queue would help. So your web-bound processes just stick stuff jobs on some queue, and some workers do their best to keep up. You could implement something like that in PHP (you might consider something like gearman or beanstalkd to provide the actual queueing).
But there's another, very specialized, option. Just use your local sendmail (assuming you're on a unix-type box). Sendmail (and the various drop-in replacements MTAs) maintains it's own queue. This stuff has been around for years and is quite solid. You can configure your MTA to pass the mail on through your current SMTP setup, too.
The difference will be that instead of your PHP script talking to the remote SMTP server, it just talks to a local service which just takes the mail, queues it, and returns in practically no time flat. It holds the mail in the queue until it can manage to send it along via SMTP.
Plain old local sendmail will go a long way towards getting you fixed up. If you're on a Windows server, I'm not sure what your options are. There must, at the very least, be a local SMTP server you can run that can be configured to relay all the mail out via SSL to google.