Yes! Storing queries that are re-used a lot is a great use of REST. I haven't implemented anything recently so no code to share with you but the client interface would be like any other REST resource. You could even POST a query that had one or more parameters that could be set when GETting the resource, so your query resource would be more extensible. For example, the resource might always query the same field name in a table, but you might pass a query string in the GET that would define what you were searching for in that field. But then you're on a slippery slope to not being RESTful anymore...

I agree that query, in general, doesn't fit into the pure REST architecture, and that POST/PUT should be used to create or update resources. I worked in a standards organization for many years and we had many "religious wars" regarding query and REST. There was never any clear answer. What we decided was to use GET with query parameters whenever possible, and when you needed a message body (for example to integrate with SOAP architecture), use POST.

The only truly REST way to handle query is to POST/PUT a query to make it a resource, then use GET to execute the query, then use DELETE to get rid of the query. But this is an awkward way to solve the problem, simply to stay truer to the spirit of a REST architecture.