Print Queues being deleted from Active Directory, even though List in Directory Ticked.

Hi Guys,
Hope you are well and can assist.

Guys we have an issue where we cannot find a printer when you do a Find Printer to list all printers in our AD.

We have ticked the box for List in Directory on each of the printer queues in question.

This is the error we get.

System Log
Event ID 41
The PrintQueue could not be found on <domain>.  It may have been deleted from the Directory.  An attempt will be made to republish the PrintQueue.  Error: 2116

I then had a look in AD Users and Computers under the computer account where it should list the printers that have been published (listed in the directory).
The printer queue was not listed, even though on the printer queue properties, it had the tick to "List in the Directory".

My question is, why would the printer queue be deleted, and if so, does it automatically republish when the tick is ticked for "List in the Directory".

It does not appear to.

Any help greatly appreciated.