I have the same problem, there seem to be no web-host (other than you) that has the Imagic PHP module activated/installed. However some web-hosts have the Image Magick application installed. I guess it would be impossible for you to add functionality with exec(); and the function “convert” or similar. This would maybe allow excecution of the Image Magick application directly rather than through the Imagic PHP module?
I also wonder if it is possible to exclude/override the Imagic PHP functionality completely in your plugin? I was thinking that all image-sizing could be done manually prior to upload and thereby making the function unnecessary. But of course if part of the function is to extract other data, such as IPTC, EXIF etc I guess the whole wonderful idea behind the plugin would get lost!