If your deleted shared printer is still listed in Active Directory, you can remove the deleted printer by:
Opening Active Directory Users and Computers
Search the root of your directory, but change the drop down from Users and Computers to Printers
Find the printer and right click and deleted it
It’s kind of annoying that when you rebuild a print server, the old printers listed in the directory don’t match the new printers on the server – obviously this is because the printers listed were associated with a computer with a different SID (a different install of Windows). The only solution is to delete the listed printers and share the new ones out.