1. Check your firewall and ensure Port 53 is open.
2. Check your Firewall/Router logs to make sure incoming DNS packets are not being blocked
3. Check for potential Network problems
4. Check that you DNS is working correctly.

DNS Caching
Disabling the "DNS Client" service on their windows 2003 server can resolve the issue, as there can be a problem with your local DNS caching.

http://support.microsoft.com/default.aspx?scid=kb;en-us;318803

IMail Only
If you are an Imail user there has been an ongoing bug in Imail with entries of multiple DNS servers in the SMTP setup page. IPswitch says you can enter several IPs separated by spaces, but if you do this, IMail occasionally gets confused and basically stops looking at DNS entirely. This results in quick buildup in the \spool and or \proc directory.

To fix this run cache-only DNS locally on the server. Just install the service, set it for Automatic, turn it on, point IMail to 127.0.0.1 and stop/start the IMail SMTP service. This will result in improved performance because all DNS lookups won't be over your network.

You can point the local DNS to your other servers by entering their addresses into DNS in the Network | TCP/IP property sheet.