Printing to Windows (not-domain) Server - Hold for Authentication

I've been printing to our windows-connected printer for ages. And then I upgraded to High Sierra and now I can't print because of the "Hold for Authentication" message.

1. I searched for a solution many times but nothing I've found has worked thus far.
2. I went into keychain and searched for the printer but it wasn't there.
3. In keychain I selected all items (logins, certificates) for that server and deleted them.
4. After deleting items from keychain, I tried printing again and got to the Hold for Authentication again and so I opened the print job and it prompted me for authentication. Nothing I tried worked. I tried my normal windows password. I tried the server administrator password. I tried no password. None of this works.
5. I deleted the printer and tried to set it up again. In the "Add" screen I browser the workgroup (called "workgroup") and selected the server (named "server") and it threw up a box "There was a problem connecting ... may not exist or it is unavailble at this time" type error.

5. I used RDP client and connected to the server using its name "server" and that worked fine (after accepting the certificate again - so I know the keychain thing was deleted properly)
6. I used the Go > Connect to server and entered smb://server and this prompted me for my details (which worked) and connected me to a regular share (which worked). So my mac CAN talk to the server under regular smb, just not printing (I deleted my keychain passwords for this site before this step to ensure they authenticated again).

7. I tried installing support for Internet Printing Protocol on the server and tried connecting to that, but that also didn't work.
8. Other Windows 7, 10 and Ubuntu clients on the same network can all print to the same printer.
9. I waited till I went home, and printed to the printer there just fine. It's the same model printer, but it's connected off my home router rather than a windows server. So as usual there's some kink between Mac and Windows.

/edit

10. I installed LPD on the server and tried connecting to it from the Mac and printing. This appears to connect to the printer (the dot turns green) and seems to print, but the page pauses and doesn't appear on the server queue at all.

I'm not sure how helpful this will be but I offer it in the hopes it will generate an idea that might work.

On a Macbook Air with Mojave I usually map directly to the printer via IP Address which is the second icon from the left in the "Add" (printer) dialog box. I find this to be more reliable than printing via our print server which is one of our Active Directory domain controllers.

However, once you select the print server (in my case it is [DOMAIN NAME] > [Print Server]) it pops up an authentication dialog box "You are attempting to connect to the server "[SERVERNAME]" Click connect to continue"

Once you click connect you get a standard login dialog box with your username already filled in.

Don't use that username or your local password there

Instead you need to enter the name of the print server, sometimes referred to as the NETBIOS name, followed by a backslash " \ " and then a username of an account on that particular server. In my case it would be something like this:

domain\stevec [password]

In your case as you are not in an AD domain:

servername\username [password]

Windows expects authorization from outside the domain to be fully qualified. EG where the credentials are, a backslash and then the account/user name.

It could be that when you try and print there are cached credentials somewhere (possibly on the server?) that are messing you up.

I would delete the printer queue from the Mac and re-add it via the Printers & Scanners preference and choose the Windows printer option and logging in as a user on that PC.

Either that or select the "Default" or "IP" methods and completely bypass printing via your Windows server, if that is possible.