Custom Post Type Template based on Taxonomy

I’m afraid you have to do this manually. You can put someting like this in your single-vehicles.php file:

if ( ... ) { // check if it's in used category/term
    get_template_part('part-single-vehicles-used');
} else {
    get_template_part('part-single-vehicles-new');
}

And then put new car template into part-single-vehicles-new.php file and used car template into part-single-vehicles-used.php.