Your order of your if/else statement is wrong. You would want to have your complex condition (or most important condition) at the top and the simplest (or least important condition) at the bottom.
if/else statements work on the basis that the first condition that hits true will be executed. In your example above, if you have a post that belongs to the specified term and post type, and you first check for either the post type or term, that condition will always ring true and fire regardless of any other condition after that, and the condition which checks whether or not your post belongs to the specified term and post type will never fire although it also rings true.
You would need to reconstruct your conditional statement to look something like
if ( 'videos' === get_post_type
&& has_term( 'featured', 'status' )
) {
// load template when post has the desired term and post type
} elseif ( 'videos' === get_post_type() ) {
// Load template for videos post post type
} elseif ( has_term( 'featured', 'status' ) ) {
// Load template for posts attached to the featured term
} elseif ( 'gallery' === get_post_type() ) {
// Load template for posts from the gallery post type
} else {
// Load a default template for all other posts
}