Make sure that the name servers that are listed in /etc/resolv.conf have not been shut down and are working properly.It's also very possible that the name servers in the /etc/resolv.conf file are working fine but the IP from where the client is accessing the server is not reverse resolvable. It can be checked with:
# host 192.168.0.1
Host 192.168.0.1 not found: 3(NXDOMAIN)
If you get 'not found' error, it is misconfiguration on the client's side, you can offer the client to contact his ISP to make the IP reverse resolvable.
Other reason for delay upon connect to SMTP service may be caused by attempt of 'tcp-env' utility to connect to identd on client side. Ident protocol had been used to obtain remote user’s name, however nowadays it is mostly obsolete and rarely used.
If client's firewall does not reject connection to port tcp/113 but drops such connections instead (i.e. just does not answer for connection request from SMTP server’s side) or if client is behind NAT and port 113 is not properly handled by the NAT, then SMTP server will send connection request to identd on client side and wait for 30 seconds to receive response. Upon timeout ident query will fail and SMTP server will continue to the next step.
To disable ident checks, options '-Rt0' need to be passed to 'tcp-env':
server_args = -Rt0 /var/qmail/bin/relaylock ....
It is necessary to restart xinetd then to apply the changes:
# /etc/init.d/xinetd restart
For Debian and FreeBSD servers that uses 'inetd' instead of 'xinetd' the option is the same '-Rt0' but the modification must be made to the /etc/inetd.conf file:
smtp stream tcp nowait root /path/to/qmail/bin/tcp-env tcp-env -Rt0 ...
smtps stream tcp nowait root /path/to/qmail/bin/tcp-env tcp-env -Rt0 ...
It is necessary to restart inetd in order for the changes to take effect:
# kill -HUP `cat /var/run/inetd.pid`
Note, /etc/inetd.conf may be overwritten and the options you added will be removed if you make certain changes through Plesk CP, for example add MAPS server.