Sorry for double post. Had some further thoughts for how to solve this and I'm not sure what is easiest to do in the MOO so I figured they'd be worth adding:
I think that having open-ended AND/OR/NOT in the search query is probably too much to ask for since it is so open-ended. But something like this would probably completely solve what I am running into:
1. Only return each node once in the results
2. Order results so that the most recently edited nodes appear first
3. Add page number and maybe excludes to the args
4. Make the args accept comma-separated values
#node-content-search
Argument: STRING – Comma-separated values (Match if ANY are found)
Optional: INTEGER -- Page number
Optional: STRING -- Comma-separated values (Exclude if ANY are found)
#endnode-content-search
(I think put the excludes after the page number because having to put a "1" when you don't care about pagination seems more reasonable to me than having to put in something to exclude just because you want to see page "2")