the unreliable part is writing good regular expressions which are not fragile in the face of simple changes to unstructured data

Ah! Now we're getting some where. I'm going to assume that you don;t consider yourself incapable of writing a good regex; which by implication suggests that you assume that wonderful catch-all, "other people", can't.

There's a really simple solution to that: regularise your error messages.

You're already advocating moving your exceptions into a single file--the Exception::Class using exception declaration module.

So, do the same thing with your error messages. And make them easy to parse:

package MyModule::Errors;

use constant {
    ERROR001 => 'MyModule::Error001: The frobwitz has a %d chance of r
+eaching critcial mass",
    ERROR002 => 'MyModule::Error002: The doobry '%s' is frazzled',
    ...
};

1;
[download]

Now all you need is:

eval { somefunc() );
if( $@ =~ m[^MyModule::Error002] ) {
    ...
};
[download]

Simple. Lightweight. Reliable.

Of course, now we're well on the way to returning error numbers instead of strings. And then providing a function (class method) that converts them to an error text (when required). With the added benefit of making I8N simple.

Don't cover up simple design issues by layering heavy & complicated code over the top. Design a solution that addresses those issues at source. In this case, the source is the string form of the error returns, not the regexes the user needs to use to handle them.