I've had a similar problem, it just was a hash of hashes of arrays (about LDIF-Format) unter Perl5.6 (under Win2k, Linux and Solaris).
I decided to use Perl5.005_03, which gave me a better performance, too

Version:           Runtime  Memory-Usage
5.0005_03 (AS522)  ~20 min  ~480 MB
5.61      (AS631)  ~90 min  ~700 MB

When I've got more time, I'll try to extract a simple script with the essential logic and commit a bug-report... because such a difference (especially in runtime) can't be true...

Best regards,
perl -le "s==*F=e=>y~\*martinF~stronat~=>s~[^\w]~~g=>chop,print"

PS: somebody has submitted a similar bug with 5.6.1 to activestate with hashes or hashes or the like...

PS2: I asked Microsoft some months ago when there came an Out-Of-Memory-Error while using about 1.2 GB RAM under Win2k, and they told me something about Memory-Fragmentation, and you could prevent it, if you preallocate the RAM (in Perl with: $#list = 10000; or the like).