You have a choice. DNS, WINS, Hosts, LMHosts or broadcast for name
resolution. Since broadcast isn't working in your case (probably
across a router) for name resolution, you get to choose which of the
others you use. You can't use DNS you said, and HOSTS file is
inconvenient. My guess is you can't/won't use WINS either, and
LMHOSTS is just as inconvenient as HOSTS. Which basically means
you're screwed.