_>Хочу чтобы нечто вроде "капуста AND валюта NOT рубли" накладывалось на "баксы валюта — капуста" и т.д.

_>Regex определяет именно набор символов, чем меня ОЧЕНЬ не устраивает.

В Regex есть знаки, означающие начало/конец слова. Никаких проблем нету преобразовать "капуста AND валюта NOT рубли" в подходящее для Regex'а выражение. Я, правда, сам Regex'ами редко пользуюсь, на память не помню.