Forgive me if I'm misunderstanding you -- but I don't see what you mean by saying that developing a schema for tagging queries would be difficult. Would something like this not work:
<match_text_containing>the search query</match_text_containing>
<skip_text_containing>stuff they didn't want</skip_text_containing>
I've been overly verbose for illustration, and there is probably a better way to set this up -- but something as simple as this would seem to work. I don't see why anything would have to be done by the user -- i.e. I don't see why they would be required to tag anything themselves. This could happen transparently whenever a search request is answered by the web server, using the values the user input in the search form, and seems to be trivial to implement. It would seem that the resources expended to save the submitted queries in this format would be trivial compared to the server resources used to perform the search itself.
Am I missing something? Sorry if I'm being stupid -- I'm not very knowledgable about this sort of thing, and it's likely that there is something simple I didn't understand...
UPDATE: Elaborated a bit on how the search queries might be formatted in the feed ...