Thanks for the suggestion, I'll try it out and check how it performs.
I wonder however if maybe the table design is flawed from the beginning.
The only other way to assign multiple product_id to the categories I can think of would be something like this:
product_id | product_category
29 | 11,14,7
35 | 12,8,1
Maybe I could then use some MySQL string functions to get the desired results, however I am not very familiar with those.