Eu finalmente consegui resolver isso sozinho. Acabei fazendo:
apt-get remove graphicsmagick-libmagick-dev-compat imagemagick imagemagick-common
apt-get autoremove
Então:
apt-get install libmagickwand-dev
E finalmente conseguimos instalar o imagick via pecl sem erros:
pecl install imagick-beta