Are you using PPTP to connect to a Microsoft ISA server for VPN? Do your internal machines on the VPN side of the connection no longer resolve except when you use a fully qualified domain name?
The PPTP VPN settings under 10.5 provide some additional options, which you can reach via the Network System Preferences panel. Go to VPN, and click on Advanced, then view the Options tab. The setting is "Send all traffic over VPN connection." If this is unchecked, you will be unable to resolve internal hostnames without typing the fully qualified domain name. If you check it, you will be able to refer to your internal hostnames by the short name. This occurs no matter whether you have your VPN local DNS search domain typed in there or not.
I think this may in fact be a bug in 10.5, since it presumably should work without have to force all the traffic over the VPN.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20071112222607232