Recently I experienced very long delays while connecting to remote mysql databases, without any apparent reason. The connect would stall while connecting, before issuing querries and would wait for about 15-20 seconds before working.
I managed to find out why: The mysqld server uses reverse DNS queries to find out the name of the calling host. If the DNS is unavailable at the server side (as was my case), it takes a while for the query to time out.
To solve this, you must add your ip and hostname in the /etc/hosts of your mysql server, so it is able to resolve your IP (or get the DNS working).
More info here: http://dev.mysql.com/doc/refman/5.0/en/dns.html