With the help from Plesk support everything is fixed now after he repaired my dns database. Also following command is useful if you want find out which domain contain a record:
plesk db "SELECT host, dns_zone_id, type, val, opt FROM dns_recs WHERE type = 'MX' and host LIKE '%example.com%'"
Now...