Like gjb said: it's not a good idea to do one replacement at a time. Why not do them all at once? It'll probably be faster too, as it wouldn't require recompiling the regex again for every substitution — 26 per sub call. You do have the hash you'd need, already.

  my $pattern = join "|", map quotemeta, keys %key:

  sub decode {
      $$message->{body} =~ s/($pattern)/$key{$1}/og;
  }
[download]

The initialization must have run before you call the sub for the first time — but that's no different from the situation like you already had, for the hash.

Note that you can't have case insensitive searches this way, or the hash entry for the matched string may not exist — though that's easily fixed. But, it doesn't seem to be necessary anyway.

For the other way around, you'll need a reverse hash.

An alternative, which will be faster in most cases, is to use the module Regex::PreSuf. That's a module to construct a regex (as a string) out of a word list. At least the most recent version takes care of the quotemeta itself.

  use Regex::PreSuf;
  my $pattern = presuf(keys %key);
[download]

Nothing else needs to change. For your case, the pattern ends up looking like:

  [\^\~\@\!\#\$\%\&\(\)\*\+\-0123456789\\\=\|]
[download]

which is rather nice.