Trouble with default search domain

Since installing Mavericks, my MacBook Pro (10.9.1) has started having trouble resolving hostnames in the default search domain, which it gets from DHCP and which shows up correctly in the DNS tab of network settings in System Preferences. Sometimes it only shows up when I try to connect to an afp or smb share in the Finder using afp://hostname, for example (I get "There was a problem connecting to the server 'hostname'"), and sometimes it also affects browsers and attempts to ping a server on the command line. However, even when I cannot ping a server by its hostname, I can still successfully do an nslookup on the same hostname. If I substitute the FQDN for the hostname, then everything works. Sometimes it seems to be all hostnames that stop working, and sometimes only specific hostnames are affected. Resetting the DNS cache doesn't help (http://support.apple.com/kb/HT5343?viewlocale=en_US&locale=en_US). The problem usually starts after the machine has been running for a while. A restart always makes it work again for a while, and then the problem always recurs.