Alright, finally fixed!!! For anyone running Miva 4.13 on a Plesk server you must do the following:
Add this to the vhost.conf and vhost_ssl.conf:
AddType application/x-miva .mv
Action application/x-miva /cgi-bin/miva
Then:
chmod 0755 ../cgi-bin/miva <--- Manual says 4755 but that...