... embedded nested ANDs or ORs. The system I'm working on would benefit from this ...

Easily enough done with an approach like that of Re: simple perl regex question (or is it?) (and probably others as well): just take whatever you get from the  $nested_parens portion of the match (with or without the enclosing ()s) and run it through the main regex again! Repeat until there is no match, i.e., no nested  AND|OR(...) to be found.