Hi mowax,

I stumbled upon your question while searching for Image::Magick information. Two tips:

1. Perl gives the "Can't locate" error when it can't properly load the module - for instance, if the Perl module (Magick.pm) exists, but refers to a library file or DLL which can't be found or which gives an error during initialization. I'm sure there's a better way to debug these problems than the one I use, but I've used SysInternals' Process Monitor in the past to track down the referenced DLLs which were having problems loading properly.
2. The quickest way to get PerlMagick on Windows is to get the binary release from ImageMagick.org. The installer searches for ActivePerl, and - if found - automatically installs PerlMagick's modules into the correct place.

Hope that helps (if you haven't figured out the problem in the last three months!)