memoize('Digest::MD5::add'); memoize('Digest::MD5::hexdigest');

No, this is plain wrong in several ways. As per the Memoize documentation:

Memoization is not a cure-all:

• Do not memoize a function whose behavior depends on program state other than its own arguments ...
• Do not memoize a function with side effects. ...

Memoizing add breaks the object's functionality. Memoizing hexdigest is wrong because the method normally modifies the object's state, plus, since it is a method that is normally only called once per object, Memoizing it isn't actually useful because the first argument to a method is a reference to the object, i.e. it will be different on every call and therefore the return value won't actually be cached across different objects.

use warnings;
use strict;
use Test::More tests=>7;
use Digest::MD5;
use Class::Method::Modifiers;

my $cnt = 0;
before 'Digest::MD5::hexdigest' => sub { $cnt++ };

my $d1 = Digest::MD5->new;
$d1->add("1");
$d1->add("1");
is $d1->hexdigest, "6512bd43d9caa6e02c990b0a82652dca";
is $d1->hexdigest, "d41d8cd98f00b204e9800998ecf8427e";
is $cnt, 2;

use Memoize;
memoize('Digest::MD5::add');
memoize('Digest::MD5::hexdigest');

# the *exact same* tests as above!
my $d2 = Digest::MD5->new;
$d2->add("1");
$d2->add("1");
# now we get the MD5 sum of "1" instead of "11"
is $d2->hexdigest, "6512bd43d9caa6e02c990b0a82652dca";
# hexdigest should reset the state of the object
is $d2->hexdigest, "d41d8cd98f00b204e9800998ecf8427e";

$cnt = 0;
my $d3 = Digest::MD5->new;
# "hexdigest" was memoized above, so should we get the MD5 sum of
# "" or of "1"? Also, should $cnt be incremented or not?
is $d3->hexdigest, "c4ca4238a0b923820dcc509a6f75849b";
is $cnt, 0;

__END__

1..7
ok 1
ok 2
ok 3
not ok 4
#   Failed test at m.pl line 27.
#          got: 'c4ca4238a0b923820dcc509a6f75849b'
#     expected: '6512bd43d9caa6e02c990b0a82652dca'
not ok 5
#   Failed test at m.pl line 29.
#          got: 'c4ca4238a0b923820dcc509a6f75849b'
#     expected: 'd41d8cd98f00b204e9800998ecf8427e'
not ok 6
#   Failed test at m.pl line 35.
#          got: 'd41d8cd98f00b204e9800998ecf8427e'
#     expected: 'c4ca4238a0b923820dcc509a6f75849b'
not ok 7
#   Failed test at m.pl line 36.
#          got: '1'
#     expected: '0'
# Looks like you failed 4 tests of 7.
[download]

Update: Oh, and your tests prove that adding Memoize slowed execution by a factor of roughly 2.2 and 13, respectively:

#Benchmarking...
#Digest::MD5	2.55
#Benchmark: running Digest::MD5, Digest::MD5::new for at least 1 CPU seconds...
#Digest::MD5: -1 wallclock secs ( 1.11 usr +  0.00 sys =  1.11 CPU) @ 138871.96/s (n=154009)
#Digest::MD5::new:  1 wallclock secs ( 1.11 usr +  0.00 sys =  1.11 CPU) @ 69872.97/s (n=77559)
#
#Benchmarking with Memoize...
#Digest::MD5	2.55
#Benchmark: running Digest::MD5, Digest::MD5::new for at least 1 CPU seconds...
#Digest::MD5:  1 wallclock secs ( 1.12 usr +  0.00 sys =  1.12 CPU) @ 61895.11/s (n=69632)
#Digest::MD5::new:  1 wallclock secs ( 1.06 usr +  0.03 sys =  1.09 CPU) @ 5227.61/s (n=5719)