There's no requirement in HTTP (or REST) to either create a resource or return a Location header.
For the purposes of caching etc, it's useful to have one, as well as cache controls for the query results, and there can be links in the result relative to the Location (eg a link href of "next" is relative to the Location).
The response to POST can return everything you need. The Location header that you receive with it will contain permanent link for making the same search request again via GET.
Pros: no practical limit on query size.
Cons: permalink is not user-friendly - you cannot figure out what filters are applied without making the request.
It adds in some data expiration problems to be solved, but its reasonably RESTful.