I've done something like that, using custom software (no framework modules, only IO::Socket/IO::Select etc) but it would probably be easy to implement using POE (provided you know POE already) for the Queue process - i.e. use a single-threaded single-process queue.

As it is now, the whole server code is about 400 lines of perl, excluding the configuration parsing and daemonizing.

If the requests are simple, you can probably write the client code in only a few lines using IO::Socket::INET. (Set up a connection to the queue process, and for each request do a $connection->print(), possibly followed by a $connection->readline to check the status).

As for threads; as long as you're not using the same connection from multiple threads at the same time, there shouldn't be any problem.