I think you will find this due to gmail semi-requiring SPF records on the sender domain. Go to the Advanced tab, Queue Management, click on one of the emails to gmail, view source and you will see a line with SPF reason with a FAIL. You can re-queue the messages and after several re-queue they will go through a few at a time. So somehow gmail is limiting/deferring any domain without an SPF record to force you to add an SPF record. Of course the emails will re-queue on their own and eventually be delivered (the delays of which you are seeing). You will need to add an SPF records similar to this: "v=spf1 mx a ptr ip4:999.999.999.999/32 ~all" to your domain. Read up on SPF records. Where 999.999.999.999 is your mx records ipaddress. Once this is added to your DNS records on the web the propagation is usually pretty quick this days (less that 10 minutes), but could take a day or more.