in reply to Match something that does not match
It seems to me like the feature you're implementing could be described as "stop matching at" (Update: or "match until") rather than do_not_match. Your current regex in do_not_match can be simplified to qr{ (?: (?!$pat) . )* }x; at least that still passes all your test cases. (This regex is pretty simple; I'm not sure if it warrants inclusion in Regexp::Common.)
Update: WebPerl Regex Tester
In Section
Seekers of Perl Wisdom