I've got problems with incoming GMAIL emails: they take 60 minutes to be processed. Emails from other providers are OK.
I installed Alfresco Community 3.4c on a Linux server (Ubuntu Server 10.10). I configured the server in order to accept incoming emails on a few folders. The configuration is OK (I was able to configure the redirection using a sub-domain with my internet provider). Several tests using http://www.mxtoolbox.com/SuperTool.aspx shows my SMTP server is OK (except I don't have any reverse DNS).
Are you saying that a message received by alfresco somehow takes an hour to show up. Or is your test that you press send in gmail and wait for the message to show up in Alfresco?
I suspect that its far more likely that GMAIL is taking time to send its emails out or your message has been waiting on a queue somewhere.