The Reason
I think you are hitting the newest Microsoft "great" move to remove Computer Browser service. (I think it was around for 25 years or so). The main reason is to stop using NetBIOS for browsing. The replacement is called WSD Provider.
The service is broken as of Windows 10 Creators 1703. If the Win10 1703 is the Master Browser only that computer has Computer Browsing. If a non-1703 is the Master Browser all the non-1703 have Computer Browsing. That is the reason why it sometimes appears to work and sometimes not. Rebooting forces a change in the Master Browser on the network.
The workaround
You have to set one computer to be the Master Browser. Maybe you can set your SAMBA to be the master browser for all non-1703 computers.
How to identify the Master Browser?
Issue the following command:
nbtstat -a YOUR_COMPUTERNAME
The computer that is Master Browser will have __MSBROWSE__ in the *Name column** e.g. ..__MSBROWSE__.<01> GROUP Registered (I'm on AD so it is little bit different but you get the idea.)
To set a computer to be a Master Browser you have to change the registry:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Browser\Parameters and change the value of MaintainServerList from Auto to Yes.
Additional to that if you are missing a String value IsDomainMaster then create it and set it to True.
On the other hand, if you are sure that you don't want your PC to take over the Master Browser role set the value of MaintainServerList from Auto to No (you may want to set it on all computers on your workgroup/network).
As for the Win10 1703 and above you may want to start the Computer Browser service and set it to Automatic.
Important to note
This is only temporary fix! Microsoft apparently decided to remove the Computer Browser service completely at some future point of time.
Edit Due to the comment - for better understanding
The win10 1703 and above update must be a client not a Master browser (must only have the Computer Browser service started and set to automatic) . The Master browser must be either pre-1703 win10 machine, win8, win7, samba, etc. The other machines will check for the Master browser and will see it if set this way. The post-1703 win10 machine will also see it but it must be a client only not a Master browser!
Answer from tukan on Stack ExchangeImportance of Master Browser in Modern domains?
Master browser
How do I set my Windows 7 computer as the master browser?
Problem with networking Windows 10, XP, and NT 4.0 together
The Reason
I think you are hitting the newest Microsoft "great" move to remove Computer Browser service. (I think it was around for 25 years or so). The main reason is to stop using NetBIOS for browsing. The replacement is called WSD Provider.
The service is broken as of Windows 10 Creators 1703. If the Win10 1703 is the Master Browser only that computer has Computer Browsing. If a non-1703 is the Master Browser all the non-1703 have Computer Browsing. That is the reason why it sometimes appears to work and sometimes not. Rebooting forces a change in the Master Browser on the network.
The workaround
You have to set one computer to be the Master Browser. Maybe you can set your SAMBA to be the master browser for all non-1703 computers.
How to identify the Master Browser?
Issue the following command:
nbtstat -a YOUR_COMPUTERNAME
The computer that is Master Browser will have __MSBROWSE__ in the *Name column** e.g. ..__MSBROWSE__.<01> GROUP Registered (I'm on AD so it is little bit different but you get the idea.)
To set a computer to be a Master Browser you have to change the registry:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Browser\Parameters and change the value of MaintainServerList from Auto to Yes.
Additional to that if you are missing a String value IsDomainMaster then create it and set it to True.
On the other hand, if you are sure that you don't want your PC to take over the Master Browser role set the value of MaintainServerList from Auto to No (you may want to set it on all computers on your workgroup/network).
As for the Win10 1703 and above you may want to start the Computer Browser service and set it to Automatic.
Important to note
This is only temporary fix! Microsoft apparently decided to remove the Computer Browser service completely at some future point of time.
Edit Due to the comment - for better understanding
The win10 1703 and above update must be a client not a Master browser (must only have the Computer Browser service started and set to automatic) . The Master browser must be either pre-1703 win10 machine, win8, win7, samba, etc. The other machines will check for the Master browser and will see it if set this way. The post-1703 win10 machine will also see it but it must be a client only not a Master browser!
You want to make sure the samba server is running SMB v3 or higher. This allows modern versions of Windows to access the server. Homegroup is not going to solve your problem.
I have tried googling this but I can't find anything that makes sense to me.
Our Domain functional level is 2008 R2.
We have an employee from another vendor stating a printer is a Master Browser within our domain, I have never heard the term but from what I can find its from the Pre-2003 days and its function is to create a list of computers within a subnet to enable "Neighbouring" (Not quite sure, But it's almost like an old way to do pathing like \\workstation\c$)
All the subnets have their own Master Browser which reports to the DC, The DC has a list of all the computers within its Browser list(?)
I'm not sure what to make of it, in all honesty it seem severely outdated and would not affect our domain in the slightest, But I do not want to disregard something when I don't understand it.
EDIT:
Found this http://www.thenetworkencyclopedia.com/entry/master-browser/ again seems very outdated.