I found the answer after I typed out the question so I’ll post it at the same time.
The solution is to set the show_in_nav_menus option to false when registering the Custom Post Type.
http://codex.wordpress.org/Function_Reference/register_post_type
show_in_nav_menus(boolean) (optional) Whether post_type is available for selection in navigation menus.
Default: value of
public argument