There is no right answer here. No solution will be perfect because no matter what you do now you have no control over how those feeds may change over time. I think you should go into this with the expectation of getting a "good enough" solution. Getting 90% of the products into the right category will probably take little effort. Getting the remaining 10% would be a lot of work.
Start by analyzing the input data to determine what attributes you can use to make a determination about the category. And, as you've pointed out this is probably different for each source of the data. I don't know how many different sources you are using. If you are using a relatively small number of sources I would look at each source individually and maybe create different logic for each one. But, if there are hundreds, then it probably isn't worth the effort. Bottom line is I can't really suggest how to go about this without doing the analysis.
But, let;s take the one example you provided where they put laptops under the category notebook. Do, an analysis of the incoming data to see if all "notebooks" are in fact laptops. If so, you can create a rule that anything indicated as a "notebook" will go into the "laptop" category. As for laptop bags being in the laptop category, you can analyze those to see if there is something in common that you can use. For example, do they all have "bag" in the name or some other piece of data that distinguishes them from laptops? If all else fails, you could use the price (although I wouldn't want to resort to it) since laptops bags "should"generally cost a lot less than an actual laptop.