String find and replace method optimization
Your code looks fairly effective, but it could be a bunch more efficient if you rearrange the code a bit, do some pre-processing, and reduce your run-time checks. Let's go through that in order....

I recommend a 'set up' stage to your code. Consider an ideal situation at runtime, the code would look something like:

public static String toUserFriendlyErrorMessage(String parcelType, String message) {

    for (Rule rule : getRules(parcelType)) {
        message = rule.process(message);
    }
    return message;
}


That would be a neat solution, where you have a bunch of rules that you know apply to the messages of a particular type, and that you can then just apply whichever ones are appropriate. That would be the most efficient at use-time too.

How would you implement that? Using some pre-processing, of course, and a new Rule class.

This preprocessing is key, and the features you should look for here are:


the rules are sorted at pre-process time.
some rules are in multiple sets of operations.
Pattern instances are compiled just once, not at use-time.


Your rules are convenient in the sense that the parcelType values seems to have an 'extension' type system:


LEDES1998B is rules LEDES1998Bheaders
LEDES98BI is the same as LEDES1998B plus the rules in LEDES98BIheaders
LEDES98BI V2 is the same as LEDES98BI (and thus LEDES1998B) but also includes LEDES98BI_V2headers


How would I recommend preprocessing things?

private static final class Rule {
    private final Pattern key;
    private final String replacement;

    Rule(String search, String rep) {
        key = Pattern.compile(search);
        replacement = Matcher.quoteReplacement(rep);
    }

    String process(String msg) {
        return key.matcher(msg).replaceAll(replacement);
    }
}


So, that rule class is simple enough... how to add them together?

private static final Map&lt;String, Rule[]&gt; RULE_MAP = buildMap();

private static final Map&lt;String, Rule[]&gt; buildMap() {
    Map&lt;String, Rule[]&gt; result = new HashMap&lt;&gt;();
    List&lt;Rule&gt; rules = new ArrayList&lt;&gt;();

    addRules(rules, LEDES1998Bheaders);
    result.put("LEDES1998B", rules.toArray(new Rule[rules.size()]));

    addRules(rules, LEDES98BIheaders);
    result.put("LEDES98BI", rules.toArray(new Rule[rules.size()]));

    addRules(rules, LEDES98BI_V2headers);
    result.put("LEDES98BI V2", rules.toArray(new Rule[rules.size()]));

    return result;
}

private static final void addRules(List&lt;Rule&gt; target, Map&lt;String,String&gt; sources) {
    for (Map.Entry&lt;String,String&gt; me : sources.entrySet()) {
        target.add(new Rule(me.getKey(), me.getValue()));
    }
}


Now, your last part is the getRules method:

private static final Rule[] getRules(String parcelType) {
    Rule[] rules = RULE_MAP.get(parcelType);
    if (rules == null) {
        throw new IllegalStateException("No rules set for type " + parcelType);
    }
    return rules;
}


Now your code should go smoothly.