It sounds like you installed onto a Unix box, try to find the actual PM file itself on the system to see if it was installed to the standard location for Perl Modules on your platform. Otherwise, it might have installed it someplace like your user home directory, which would be why it is not in @INC. Try a command like:

$ find / -name Rule.pm 2>/dev/null