Perl Best Practices covers this issue well. Objects are the thing to throw.

I disagree with some of your ideas:

• Warnings should be meaningful. A warning that needs no action can be ignored, then will be ignored, then just becomes useless verbiage. Make it an error or silence it.
• "Fatal errors" are a self defining group. You don't need to tag them so. Update: I wish I hadn't said that. It is true, but if you know your exception should be fatal you should capture that information in the exception. One just needs to be careful of unwarranted assumptions about the calling environment.
• Always provide the line number of the error and/or the caller. If some part of the code doesn't handle input correctly, you will need to know which code that is.

Like Best Practices I would suggest using objects, in your first pass use the object type and the long output of a bare croak, in your message clean up phase use another method to output the exceptions' error strings. Since these methods or the table they use doesn't exist the brokenness forces the fix; examining your type tree gives you a list of all your errors and their meanings then you just need express them. This implies handler objects or another way of consolidating your error handling code.

You may complain that I've only moved your problem to the naming of exception packages. I won't argue.

Be well,
rir