I've never had an issue with Debian's ImageMagick. I can only imagine that you're on an OpenVZ VPS, to encounter such an issue. I've used ImageMagick with Wakaba on a 128MB VPS. Of course, this is in terms of having one image uploaded at any time. I'm sure you would start to encounter timeouts in various pieces of software if you were uploading multiple high resolution images at the same time, consistently throughout the day.

Any 512MB or higher Xen/HVM should be perfectly fine, though.