After spending a small eternity googling for the answer I found it.
First -- The problem:
You have a linux box getting its IP address from a Win2k DHCP server.
Your resolv.conf looks like this:
search xyz.com\000 nameserver 10.1.1.1 nameserver 10.1.2.1
The \000 at the end is screwing up name resolves.
Fix:
The problem's in /etc/dhclient-script.
Line 36:
echo search $new_domain_name >/etc/resolv.conf
Change this to:
echo -e search $new_domain_name >/etc/resolv.conf