One thing that this tells me is that the `perl` being used in your CGI environment is not the one for which your I::M module was installed. Fwiw, when Image::Magick is typically installed when the ImageMagick bin utils are installed (e.g., `convert`). It is possible that the Perl module was installed in a non-standard location, but typically it goes into the default @INC location for the system `perl`. You may want to confirm with your provider that they installed it properly - or at least for the same `perl` you're using in your CGI scripts.

If you're using a VPS, does this mean you have root access to the "box"? If so you can add PERL5LIB envar to your Apache httpd.conf file. Even if not, you should be able to request the ability to maintain your own .htaccess file. This would allow you to set an appropriate environmental variable with the proper Perl path to I::M.