You'd have to have an instance of the thing you are trying to create

Fair point. One could require a simple string constructor or something along these lines, but that is of course not enforceable. An alternative is to use serialization and custom writeObject and readObject. At least the functionality is where it belongs. Also, one still could keep the toLuceneQuery instead of having this rather strange indirection via getQueryKey.

So let's say we'd move the toLuceneQuery(...) and toString() to the DeletionQuery and keep the fromString(...) somewhere else. Then we'd end up with code scattered all over the place and I don't like that.

I don't think it is scattered. It is where it belongs. The code to create a Lucene query from a DeletionQuery belongs into the DeletionQuery itself. In your case for each query type we support we keep adding to DeleteByQuerySupport making an already hard to understand class even more unyielding.