Custom Taxonomy returns no posts

Finally I’ve figured it out, I didn’t elaborate on this in my question but I had exclude_from_search set to true on register_post_type which is obviously why no posts were being displayed in the taxonomy-video_category.php template file.

Changed it to false and posts are now displayed.

// ...

$args = array(
    'labels' => $labels,
    'description' => 'Holds our Videos and Video specific data',
    'public' => true,
    'exclude_from_search' => false,
    'menu_position' => 5,
    'supports' => array('title', 'editor', 'page-attributes', 'thumbnail'),
    'has_archive' => true,
    'rewrite' => array('slug' => 'how-to-videos')
);

register_post_type('video', $args);

// ...

Further explanation on exclude_from_search in this question.