When you browse to a UNC, you are actually using NetBIOS initially, not DNS. The order of lookup resolution is:
1. Local NETBIOS cache (including #PRE entries from LMHosts)
2. WINS (if configured and the client is a H node)
3. NetBIOS broadcast
4. LMHosts (all entries including those not marked as #PRE)
5. Local DNS cache
6. Hosts file
7. DNS server
So, looking at this logically - the machines on another subnet cannot be resolved using NetBIOS unless you have a WINS server set up (because broadcasts do not cross subnets). So if you do not have WINS, steps 1-4 will fail (unless you have added entried into LMHosts)
A machine will automatically append it's own DNS suffix to an un-qualified name in order to try to resolve it. So while steps 1-4 were looking for 'server', steps 5-7 are looking for 'server.domain.local' on the DNS server. Check to see if these entries are on the DNS server.
But If a machine is not on the domain, unless you have configured a DNS suffix on it, it will not be able to resolve other hosts using an unqualified name.
If you have a mix of domain/non domain machines and you want to easily be able to resolve un-qualified names across both subnets, then I'd recommend setting up WINS on a server, then in your DHCP scope, configure all your clients to use this WINS server and make them 'H' node types.
I think this would be the simplest method.
