chmod +x xxx.cgi
してもだめ？
俺のとこでは
chmod -x xxx.cgi
でエラーメッセージの再現はできるけど。。。
apacheのユーザー分かる？wwwとかだったら
sudo -u www -H /usr/local/bin/perl -w xxx.cgi
するとどうなる？

＞Image:MagickそのものかPerlがモジュールを探せられて無いのかイマイチ原因が突き止められません

#!/usr/local/bin/perl -w
use strict;
use Image::Magick;
print "Content-Type: text/html\n\nok!";