That's very weird. Is the category/term logic set to “AND” on the General options -> Category/Term logic panel? https://i.imgur.com/IPdFBKK.png If it's set to OR, then if the product is in multiple categories, then it will show up unless all the container categories are excluded.
If that option is set to AND, then this must be an unknown issue yet. I'm unable to replicate it on my test servers unfortunately.
Can you provide temporary admin and ftp access to your site? I would like to do some debugging on the search code to find out why that product still shows up.
Could you also tell me what to look for, and which product should not show up?Best,
If you like my products, don't forget to rate them on codecanyon :)