Ok, I have the exact same problem. Old Deployed Printers are unable to be removed.
I found that you can remove them from the hidden devices Printer Queues node of Device Manager (turn on Show Hidden Devices and expland the Print Queues Node) and they actually go away. I haven't tried scripting this with PowerShell yet but I see that it might be possible.
First, remove all references to the disconnected print server from the registry. I removed all references that included the old print server name. The printers now showed in the Printers and Devices list as Disconnected. I then opened Device Manager and removed the hidden print queues.
At this point, the printers disappeared from the list of Printers and Devices and did not return on reboots and logins.