I've mapped base 32 to 'A'..'Z', 0 .. 5, but you could use any set of 32 symbols that you like:

use Digest::MD5 qw[ md5 ];
sub md5_base32{ 
    join'',map{ 
        ('A'..'Z', 0..5 )[ ord pack 'b5', $_ ] 
    } unpack '(A5)*', unpack'b*', md5( $_[ 0 ] ) 
}

print md5_base32( 'fred' );

XSCAZ54XMU5W0OVYUWYRGZU0RF
[download]

Note that the last digit will always be 0..5/'A'..'F', but that's probably okay for your purpose.

Update: A slightly more efficient version:

sub md5_base32_2{ 
    join'', ('A'..'Z', 0..5 )[ 
        unpack 'C*', 
          pack '(b5)*', 
        unpack '(A5)*', 
        unpack 'b*', 
           md5 $_[ 0 ] 
    ] 
}
[download]