DNS problem - internal random host names resolve to our external website address

Here is the issue: we have our internal domain as local.company.com
Our external domain is company.com
Netbios domain name is "company"
we use wildcard in our A record at Netsol:
@.company.com       (None)    7200               ourwebsiteip
*.company.com        (All other)    7200           ourwebsiteip
All internal severs running Win2003 SP2.
Problem is when we try to ping any random host (non FDQN), it resolves to our website IP:
so if we do   "ping kjhkjhkjh"  we would get reply back from our website address.
Internally, we have two DNS servers. Both list themselves as primary, and each other as secondary. No external DNS servers listed in TCP/IP properties. When running nslookup with -d2 option, I can see it tries to resolve to kjhkjhkjh.local.company.com first, then if it doesnt exist, it tries kjhkjhkjh.company.com and that's where it returns our web site address. How can we stop it from going out and returning our website address to every invalid hostname request (without removing wildcard from our domain name at Netsol)?