>>> Yes, this is a harder problem.  We have to remember meta-data for
>>> every search history element.  There are several possibilities:
>>>
>>> 4. Adding meta-data by text-properties to the strings in
>>>    ‘search-ring’ and ‘regexp-search-ring’ poses a problem of saving
>>>    the values in the desktop and restoring in another session.
>>
>> This feels like the best solution. I looked at desktop.el, and it
>> doesn't save the properties, as you say. But it could be made to. Do you
>> think some external packages would get broken by this change?
>
> This seems to be the least radical change as concluded in
> https://lists.gnu.org/archive/html/emacs-devel/2018-03/msg00296.html
> The patch makes the search mode to be remembered in isearch as well as
> in query-replace.

As predicted, the solution with using text properties caused more trouble:

1. To be able to use ‘C-s M-p’ and restore a previous symbol isearch
   it was necessary to let-bind minibuffer-allow-text-properties to t
   in isearch-edit-string.

2. To use a previous replacement with text properties required to replace
   ‘substring-no-properties’ with ‘substring’ in ‘query-replace--split-string’.

3. For the same purpose to use e.g. ‘M-% M-p RET’ also required to completely
   rewrite ‘query-replace-descr’ to keep text properties non-destructively
   in the replacement string.

I'm not sure if I found all problems or there will be more trouble,
but at least these fixes were necessary for this patch: