Your @INC looks a little unusual to me. Is this a custom built Perl or the system Perl? Are you setting PERL5LIB or similar?
Assuming this is the system Perl, my approach would be to pick apart which files in the @INC paths belong to packages managed by the system and delete the rest. "debsums" may be helpful here, along with forced reinstalls of the packages.
Then, once you've cleaned up the system Perl, only use the package manager to add or remove modules there. For custom built modules I would suggest building those in a local build of Perl (perlbrew), this eliminates the risk of messing up the system Perl.