I'd like to know what's changed (in Windows) and how to get it all working again please.
Hint: It's not the Windows client's fault.
With Window Vista, the "good old unreliable" method of discovering computers in the "neighborhood" using SMBv1 has been deprecated. All the newer boxes are using "Web Services Dynamic Discovery (WS-Discovery)" since then. Depending on your configuration, it's most likely that your SMBv1 listener is finally turned off (and it should stay this way). It's no longer supported, anyway.
So, discovery of (linux-) computers is no longer a matter of Samba "alone" answering. Like your typical mac it must answer to WSD calls now.
I believe Version 20.04 of the KDE Applications package kio-extras will support SMB host discovery using WS-Discovery, but that version is not available in the Stable Branch of Gentoo Linux installed on my main laptop, nor in Lubuntu 18.04.
A (tested) WS-Discovery service for linux is wsdd. It's a Web Service Discovery host daemon.
wsdd implements a Web Service Discovery host daemon. This enables (Samba)
hosts, like your local NAS device, to be found by Web Service Discovery
Clients like Windows.