I know you said you tried everything, but did you disable auto login of net shares? And assuming your net shares are set up without a password (recommended) you should just be logging in anonymously with no password (IOW, not touching anything but just moving down to login). That’s what you’re doing, right?
It might help to know what your network is (what OS, how many computers are doing what) and what’s on when you turn on the Live for the first time.
I have to admit that while I never have an issue with my NAS on my network, I now notice (never really paid much attention to it before) that my net shares for the other machines do come and go at various times. I don’t normally access them anyway (because I’m usually using the NAS) but every now and then when my NAS isn’t on I will go out to another share and now I find there is an inconsistency in what is available. Because I have a LOT of machines and because they have different OSs it’s hard to find a pattern (and it’s also hard to get “stuck” because I can always find some machine that has what I want to see) but I can see a situation where others might be in difficulties if their choices are more limited.
OTOH, my NAS works ALL the time, no matter what – so it’s something to consider (and it’s cheap and much cheaper to run than a computer all the time).