Oh, then it may explain the issue. From what I can see the CPT-onomies plugin turns post types into taxonomies? That could mean, that the terms does not actually exist in the database (?), only some sort of relation to the post types. At least it would perfectly explain why it’s not finding them.
The taxonomy can be registered, but that does not mean that the terms exist in the database. That is probably why the link pointing to the taxonomy term page does not work, and redirects to the post type page. If these does not exist, the only way to filter them is after the search process with a custom function, which will be extremely slow – as all results have to be parsed from the database individually, as well as all categories for each post. That is probably what the LSFC plugin is doing, and why it is slow. This search filters during the search query, which is much efficient, but if the terms does not exist in the database, it fails.