For the toString(...) and fromString(...) methods (or anything similar to this) I don't really want these to be handled via serialization

This is not serialization per se. You would be in full control on how you do it. An other alternative would be to have a abstract base class for DeletionQuery with a static factory method for {{DeletionQuery}}s. One might be able to extract some common functionality into this abstract class as well. Anyways, ...

maybe just don't make them inner classes of DeleteByQuerySupport but a separate class encapsulating that logic.

That might be a step forward. The current class is really hard to read with all its inner (anonymous) classes and so on.