Well, checkinstall -D 'make install' should have made full package of perl, with everything that make install was going to install. It can be checked using dpkg-deb -c file.deb. Maybe the problem is not caused by perl itself, but by some package that was installed on the building machine as perl dependency, but not on the others.