To be honest, there is no correct or wrong answer here. I do believe that templates are theme territory, although custom post types and taxonomies belongs in a plugin
The reasoning behind this is
-
HTML mark up across the theme should be uniform. For instance, if you have templates in a plugin, and you have customized it for the current theme, it will most probably break your CSS styling in a new theme if you decide to change themes
-
This is an extension to the previous point, HTML are almost never the same between themes
-
Theme specific functions will lead to fatal errors when a theme is changed if your template is in a plugin and the new theme calls this template
This is just one or two points you should consider. I might have slipped one or two, but these are the important ones
These templates will not be used once the plugin is deactivated if they are specifically named to be used for that particular post type or taxonomy, so you need not be worried about these templates breaking something. If ever a taxonomy or post type is registered with the same name, these templates will most probably just be used without any issues
So, to conclude, this is up to you what you want to do. At the end of the day, you need to keep your site and code as manageable to yourself as possible so that in 5 years time you still know exactly what is going on with your site and code