Determining if a printer can handle a print job without look-up

Solution 1:

More aggressive caching. Have the client perform the look-up once and persist the cache between restarts. Better yet, save the cache to a central data store which is accessible by all clients.

I'm assuming that network printers and their capabilities don't change that often but you have to update the cache eventually, but the "who" and "when" is dependent on your environment.

Updates to the cache can be made by a client that runs your current discovery in the background and if changes are detected updates the cache. If you have a central component that runs continuously anyway, that would be a good place where you can check in fixed intervals.

If you have some kind of directory service you can compare its list of printers with you cache before contacting each printer to get its capabilities to lessen network and cpu load.