Confused with attachment mimetype order

Yes, this does seem like a lapse in template hierarchy.

The easiest for case described would probably be handling logic in image.php, along the lines of (see get_attachment_template() for mime type retrieval):

if( 'gif' === $subtype ) {

    include 'gif.php';
}
else {

    // generic image template
}

For more complicated logic it might be worth just ignoring native order and overriding it with custom one for this branch of hierarchy.