Hell, not only do you need regexes, you need the ability to run arbitrary programs and make decisons based on their exitcodes, or, possibly, command-line output: allowing shell fragments, or something like them, works well here. You need the ability to do *multiple* things if a test passes or fails, which means you need conditionals and a block structure.
The syntax may be rebarbative, but procmailrc surely is a language.