One thing to check is that the DNS servers in /etc/resolv.conf are answering quickly (dig some_name.domain @server_ip).
The server runs no DNS server itself.
I ran dig www.google.it @213.179.193.200 (ie the complete real IP of my primary dns server as listed in /etc/resolv.conf) and this is the result: [root@vps728 ~]# dig www.google.it @213.179.193.200
; <<>> DiG 9.2.4 <<>> www.google.it @213.179.193.200 ; (1 server found) ;; global options: printcmd ;; Got answer: ;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 37012 ;; flags: qr rd ra; QUERY: 1, ANSWER: 3, AUTHORITY: 4, ADDITIONAL: 0
;; QUESTION SECTION: ;www.google.it. IN A
;; ANSWER SECTION: www.google.it. 300 IN A 173.194.35.151 www.google.it. 300 IN A 173.194.35.152 www.google.it. 300 IN A 173.194.35.159
;; AUTHORITY SECTION: google.it. 10800 IN NS ns2.google.com. google.it. 10800 IN NS ns3.google.com. google.it. 10800 IN NS ns4.google.com. google.it. 10800 IN NS ns1.google.com.
;; Query time: 2011 msec ;; SERVER: 213.179.193.200#53(213.179.193.200) ;; WHEN: Thu Sep 6 13:41:43 2012 ;; MSG SIZE rcvd: 161
as far as the queue goes, it was empty. I run postsuper -d ALL and postuper -d ALL deferred, just in case, but no change
Thanks, Marco