Unable to resolve local lan hostnames

As a fairly recent Mac convert, one of life's little niggles is the seeming inability of Tiger (10.4.8) to resolve the names of WinXp PCs on the local LAN. I can browse to them fine, set up shares to them, use smbclient to them, but can't ping them or use their names in things like VNC or RDC.

I know I can put names in the etc/hosts file, but that dictates using static IP addresses, which I'd rather not do. I've seen many other posts regarding this problem, but no obvious solutions. Anyone got one?

Thanks!