What methodology is being used to poll SQL instances when using sqlcmd with the -L switch? I've discovered that issuing sqlcmd -L from the console of a SQL host in my network only reveals other instances on the same subnet. It used to reveal all instances on the network so I was wondering if an O/S or network firewall rule is blocking polling attempts outside the subnet. What firewall rule can I asked my network engineers to establish to allow polling for instances beyond the immediate subnet?
SQL Server discovery is attempted using UDP port 1434.

You'd need to get UDP traffic destined for 255.255.255.255 on port 1434 opened in your local router to see servers from other subnets.  

See http://www.mssqltips.com/sqlservertip/2057/why-listing-all-of-your-sql-servers-does-not-always-work/ for more info.