Why would a hosting company not provide ImageMagick on a shared server?
I use Stablehost's shared server services and have access to all PHP options including ImageMagick.  Some hosts choose to restrict access to these functions in order to reduce the number of "complex" websites on their server so they can cram more websites on their server. Most reputable shared hosts provide resource usage limits that they define as acceptable for their service.  Restricting what libraries you can use is a poor business choice.

While this isn't a CiviCRM question - I think questions around webhosts and what they offer are important. I hope you get VidaHost to enable it for you - if they don't - take your business elsewhere.