It is weird situation that new order email is not sending properly from magento shopping cart.
I have used sendgrid for mail sending most of case and never know about the queuing mechanism at Magento at all.
And this this I was using the SMTP Pro Email Extension that has Queue configuration that was bother to send email through gmail smtp server.
All you have to do is System ->configuration -> SMTP Pro and select the “Queue Usage” as “Never” as below image;