Specifically, regarding access lists blocking NetBIOS traffic, you would be looking for ports 137, 138, 139, and maybe 135 too. But I doubt this is it, if the servers show up sometimes and other times not. Not much else on a router or switch that would cause this, except maybe unstable links.
Assuming links are stable, servers being browsable then not browsable (in the Microsoft Networking sense, not the HTTP web browser sense) on remote subnets may indicate problems with master browsers or domain master browsers on those subnets. Either that, or WINS or DNS services may be down/stopped. Or both.
Microsoft Networking has a history of being somewhat troublesome when using TCP/IP across subnets. Specifically, the issue of resolving NetBIOS names to IP addresses. NetBIOS was never intended for use in a routed environment. Microsoft Windows Internet Name Service (WINS) and Domain Name System (DNS) servers work pretty well to overcome these difficulties, but they are not always 100% reliable.
Not sure if this will help Veritas software, but it won't hurt to give it a try. If you know the names of the servers you want to back up, and you know what their IP addresses are, you can guarantee 100% name-to-IP-address resolution on your backup server by creating LMHOSTS and HOSTS files.
There is usually a sample LMHOSTS file (called LMHOSTS.SAM) in the C:\WINNT\System32\Drivers\Etc directory. Copy it to LMHOSTS (no filename extension). Then,
1. Edit the LMHOSTS file.
2. Add IP addresses and server NetBIOS names.
3. Put #PRE at the end of the line if you want the address to be cached into memory. (Otherwise, Windows will search the LMHOSTS file if the name is not found in the cache; this will take a little longer.)
4. Save the LMHOSTS file.
5. Run the command line utility NBTSTAT -R. The -R parameter re-reads the LMHOSTS file and adds lines with #PRE to the name cache.
As for the HOSTS file, if you don't have one or the one you have is the default (that is, only one entry 127.0.0.1 localhost), just copy the LMHOSTS file to HOSTS. Anything after the first # character on each line will be ignored.
These files will not preclude use of WINS and DNS, they are actually referenced before WINS and DNS servers are queried.
Hope this helps.
