1. Try scanning @INC looking for the .pm files. Or you could fork(), (so the memory used by the module isn't left around afterwards) then require the module
2. It prompts the user for configuration :-). Ideally the CPAN module should auto-configure CPAN mirror selection with <cite>netselect(8)</cite>
3. it is usually linked in /usr/lib/sendmail or /usr/sbin/sendmail, otherwise look for it in $ENV{PATH}. If you can install Net::SMTP then you can alter the nature of this configuration problem, as others have mentioned.

Try the install of RT for one approach to the problem. It basically has a step-by-step guide, and a script that tests the configuration and provides appropriate configuration advice.