Parche

Tras perder una ingente cantidad de horas tratando de comprender y resolver el problema, di con un workaround, que es ejecutar este ficherito. Llamémoslo reiniciar_impresoras.bat: 

sc stop spooler
taskkill /f /im splwow64.exe
sc start spooler

Básicamente, lo que hace es parar el proceso Cola de impresión (spooler), matar todos los subprocesos splwow64.exe colgados que queden y volver a levantar el servicio.

Vamos, lo que todo el mundo conoce como apagar y volver a encender, pero solo del proceso colgado.

Nuevo problema

Tienes que ser el Administrador para que esto funcione. Claro, en un entorno con más de 20 usuarios, no puedo dar esos permisos a cualquiera.

Dando permisos por servicio a los usuarios

Lo primero que vamos a hacer es respaldar los permisos actuales del servicio, para poder restaurarlos en caso de romperlo todo involuntariamente (cosa bastante fácil con estos asuntos). Para ello, ejecuta como administrador este comando y guarda bien todo el texto que te devuelva: 

sc sdshow spooler

En mi caso devuelve:

D:(A;;CCLCSWLOCRRC;;;AU)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWRPWPDTLOCR‌​RC;;;SY)S:(AU;FA;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;WD)

Como todo el entorno está montado con un Active Directory (llamémoslo MiDominio), crea un grupo de usuarios al que le daremos luego permiso para reiniciar ese servicio. Lo llamaremos ReiniciarImpresoras.

Descárgate la utilidad SetACL (versión Administrators).

Ahora, siguiendo las instrucciones y la documentación, estableceremos el permiso para que los usuarios del grupo ReinicarImpresoras puedan reiniciar el servicio de Cola de impresión. Supongamos que la máquina en la que estamos trabajando se llama MiMaquina. Ejecuta lo siguiente como administrador: 

SetACL.exe -on \MiMaquina\spooler -ot srv -actn ace -ace "n:MiDominio\ReiniciarImpresoras;p:start_stop"

Ahora tus usuarios podrán ejecutar el script reiniciar_impresoras.bat cada vez que se les bloqueen.