SMB-shared printer visible, but can no longer connect to it

tl;dr: Uninstall Windows updates KB5006670 and/or KB5005565.

(Credit to @harrymc for this answer.)

On October 12th, computers running Windows 10 received an automatic update from Microsoft, KB5006670. It has been reported that (emphasis mine):

The recently released ... update is just the latest in a long string of updates that have led to problems for Windows 10 users. People whose systems have been negatively affected by the update report being unable to connect to network printers while seeing 0x00000709 and Element not found errors.

See also an item on the BleepingComputer website's MS news channel:

New Windows 10 KB5006670 update breaks network printing

based on a long thread on their forum, with sysadmins ranting about this prob. In the future, you may want to consult that forum if you don't find an issue addressed here on SU.

This follows a similar problem last month, with Windows Update KB5005565, released September 14th.

In my case, the users' computers had the later update (6670). Uninstalling it allowed connecting to the network printer and printing seems to work (have not tried all machines yet).

Summary of the above discussion:

On the face of it, a working setup suddenly stopped working, where the Windows 10 computers were suddenly unable to connect to the network printer.

After some verification, the only explanation left was Windows update, which is after all one of the greatest dangers for system stability.

The candidate updates were KB5005539 and KB5006670.

A search found the article KB5006670 is the latest Window update to cause printer problems, which said:

People whose systems have been negatively affected by the update report being unable to connect to network printers

The removal of KB5006670 did fix the problem and network connectivity was restored to the printers.

For hiding unwanted Windows updates, see the article How to Hide or Show Windows Updates in Windows 10, which also provides a download of the Microsoft Troubleshooter (which Microsoft does not provide any more).