Does Java have an indexable multi-queue thread pool?

For each id, you need a SerialExecutor, described in the documentation of java.util.concurrent.Executor. All serial executors delegate work to a ThreadPoolExecutor with given corePoolSize.

Opimized version of SerialExecutor can be found at my code samples.

If you don't find something that does this out of the box, it shouldn't be hard to roll your own. One thing you could do is to wrap each task in a simple class that reads on a queue unique per id, e.g.:

public static class SerialCaller<T> implements Callable<T> {
    private final BlockingQueue<Caller<T>> delegates;

    public SerialCaller(BLockingQueue<Caller<T>> delegates) {
        this.delegates = delegates;
    }

    public T call() throws Exception {
        return delegates.take().call();
    }
}

It should be easy to maintain a map of ids to queues for submitting tasks. That satisfies condition (1), and then you can look for simple solutions to condition (2), such as Executors. newFixedThreadPool

I think that the simplest solution is to just have a separate queue for each index and a separate executor (with one thread) for each queue.

The only thing you could achieve with a more complex solution would be to use fewer threads, but if the number of indexes is small and bounded that's probably not worth the effort.