@jimp:
When testing with DNS tools, always end a fully qualified domain name with a "." - otherwise it will assume you want to append your system's search domain.
So to lookup "www.google.com" you must use "www.google.com."
The most common way that you see the behavior you are getting is if "mydomain.com" has wildcard DNS enabled, so it's responding to any query with the same reply.
Due to the search domain being used, it ends up getting a response for a query that usually fails.
So your problem could be solved by disabling wildcard DNS on your domain name.
try without www, don't use it at all.