Re Autoloader, I did consider it, but all of the modules are required, so I have to take the hit at some point. Admittedly, there is something to be said for spreading the pain a bit :-)
Re DProf, I find it very useful for general tuning, but do not think it will help me diagnose compile time performance issues. I find strace more helpful for that.
Re stat calls, I already set up @INC so that only the required dirs are on the path and the dirs are in decreasing order of used modules, in order to obtain the lowest number of open failures.
Perl does not actually issue stat calls when looking for .pm files. It just issues open calls and gets ENOENT if they are not there. stat calls are issued for .pmc, .so and .bs files (there may be others). In my example, the vast majority of stat calls are for .pmc files.
Re the stat calls not being the problem, I can see from the strace output that they are taking around three seconds, which is a significant part of the startup time.