I am sure someone will disagree, but i think your approach is fine (apart from the caveats you mention). An alternate approach might be to make a totally unique id, that fits your requrements (I can't remember where i originally found this code - sorry if it is you!):

sub generate_random_string { 
    my $length_of_randomstring = shift;    # the length of the random 
+string to generate 
    my @chars=('a'..'z','A'..'Z','0'..'9','_'); 
    my $random_string; foreach (1..$length_of_randomstring) { 
        # rand @chars will generate a random # number between 0 and sc
+alar @chars 
        $random_string.=$chars[rand @chars]; 
    } 
        return $random_string; 
}
[download]

Or is should imagine there are random id generators on CPAN...

And associate that with the readable id using a lookup table or similar(I assume this is why you want to keep them "as similar as possible"?). You can then convert between the two for printing purposes, but for storage, all your entries have a proper (but non-sensical) random and unique id.

Just my opinion, but i hope it helps...