OK, nobody wants to do this, possibly because of too simple solution.

I've made this myself by editing core/icon_api.php and changing $g_status_icon_arr there:
$g_status_icon_arr = array (
NONE => 'priority_low_3.gif',
LOW => 'priority_low_2.gif',
NORMAL => 'mantis-space.gif',
HIGH => 'priority_1.gif',
URGENT => 'priority_2.gif',
IMMEDIATE => 'priority_3.gif'
);

And of course, I've added new icons into images dir. I'll upload them here.

I agree, this is too easy not to do. One has to decide though what "none" and "normal" should mean. Since if there is no priority it isn't set yet and should not be considered low. It should maybe be a '?' or something. It for sure shall not be lower then low. Low can be an priority_1.gif mirrored and colored blue.

I added the 3 icons, but used the following default:

Icon associative arrays

Status to icon mapping

$g_status_icon_arr = array (
NONE => '',
LOW => 'priority_low_1.gif',
NORMAL => '',
HIGH => 'priority_1.gif',
URGENT => 'priority_2.gif',
IMMEDIATE => 'priority_3.gif'
);