Is it possible to force Craft to recheck available sever modules?
Craft will re-run the requirement checks simply by loading that admin/utils/serverinfo page.  The results aren't cached.

It sounds like your box may have had the ImageMagic library installed, but not the PHP wrapper for it.  You can check by going to admin/utils/phpinfo and searching for imagick and if there are no results, it's not installed.

Alternatively maybe it is installed, but you're explicitly setting the imageDriver config setting to 'gd'.  Be default, it's set to null which means Craft will automatically use Imagick if it sees its available.