Printer not found - print a testpage and printing works

Does the client has the same driver with the terminal services printers?

Which client are you using?
Try to remove the print driver completely and then try to install it again.

http://www.wincert.net/tips/microsoft-windows/windows-7/2174-how-to-remove-the-print-drivers-from-windows-7-machine.html

Regards

Kakosi: Printing is done through the server. We do not use printer redirection on the client. I suppose that was what you were asking?

Can you give as some details apout your enviroment?
Users work through terminal services?
or you just connected the printer on the client via the server?

The users are working through terminal services. The printers are installed on a printserver and mapped onto the terminalserver. The drivers for the printers in question are all the same release.

We do not use client printer redirection. In my opinion it is like the printer is not found by the application until I print a testpage. Can printerdrivers "fall asleep"?  

You should add the same drivers on your terminal services as well,not install add .
http://technet.microsoft.com/en-us/library/cc732946.aspx

check my comment on the bottom of the page.  This might apply to you.

https://www.experts-exchange.com/questions/26380144/Can-I-use-local-printers-with-a-remote-app-on-server-2008.html?cid=238

is it only a single user or random users and also if administrator are also having the same problem?

what's the OS of your client system? Is that the only system which is having his problem?

remove printer completely from the system and also from registry i.e.
hklm\software\microsoft\windows nt\currentversion\print\printers\(your printer)

now add the printer and see if you are still having the same problem

kakosi: I checked all three servers, they have the same drivers installed in printermanagement.

Mahrens007: I cannot disable all remote printers as we have remote users who need to print from home. But all office-users do not use printer-redirection.

agtech: random users expirience this type of error. I comes periodicly. Today for example, one user had the problem. I could print at testpage without problem. Word did not want to print. I had to reinstall the printer for the user before Word would print.

Please remove the printer completely (also from registry) as I have mentioned above and then reinstall it.

We have upgraded our VMWare from ESX 3.5 to ESXi 4.1 and haven't expirienced the problem since. Our DC's and some other servers are running virtual. It seems weired to me. But if the problem shows up again, I will try remove all printers and install them again. Thanks for your input, but since the problem is gone I cannot accept your input as solution. :-(

We found the solution ourselves.