Yes, it is reasonable to expect the host to take care of those sorts of details. In fact, it should be installed into somewhere in @INC by default. Are you sure it's installed? Maybe they installed ImageMagick and not PerlMagick (Image::Magick)?

Update: Like fglock noticed, you're mispelling Image::Magick.