is there a reason why the aix-thread-multi is in there twice?

That's normal.

You could try something like

$ truss /usr/bin/perl -MMIME::Base64 -e1 2>&1 | grep Base64
[download]

to see which paths are actually being visited while searching, and compare the output against the system where your script works. 

For instance, on an AIX 5.3 machine (the closest I currently have available to your setup) I do get (which is working fine):

statx("/usr/opt/perl5/lib/5.8.2/aix-thread-multi/MIME/Base64.pmc", 0x2
+FF21CA0, 128, 010) Err#2  ENOENT
open("/usr/opt/perl5/lib/5.8.2/aix-thread-multi/MIME/Base64.pm", O_RDO
+NLY|O_LARGEFILE) = 4
statx("/usr/opt/perl5/lib/5.8.2/aix-thread-multi/auto/MIME/Base64", 0x
+30008738, 128, 010) = 0
statx("/usr/opt/perl5/lib/5.8.2/aix-thread-multi/auto/MIME/Base64/Base
+64.so", 0x30008738, 128, 010) = 0
statx("/usr/opt/perl5/lib/5.8.2/aix-thread-multi/auto/MIME/Base64/Base
+64.bs", 0x30008738, 128, 010) = 0
[download]

Then, compare the .pm-version to the .so-version (with the respective paths as revealed by truss):

$ grep VERSION /usr/opt/perl5/lib/5.8.2/aix-thread-multi/MIME/Base64.p
+m
use vars qw(@ISA @EXPORT $VERSION $OLD_CODE);
$VERSION = '2.21';
eval { bootstrap MIME::Base64 $VERSION; };

$ strings /usr/opt/perl5/lib/5.8.2/aix-thread-multi/auto/MIME/Base64/B
+ase64.so | grep ^[0-9]
2.21
2.21
[download]

(the version numbers should be the same)