We are on Magento CE-2.3.5 and have been experiencing this issue since upgrading from 2.2.8 a few months ago.
When our team is making product changes/updates and we run indexer:reindex; all products are in their correct category assignments but eventually we notice the products begin to appear under different categories that they are not assigned to, and get removed from the ones they are assigned to. They additionally get removed from being searchable, however a direct product URL does still work to display them. This only lasts until we run indexer:reindex, but does require constant monitoring and of course running the command EVERY time.
It's always the same products that this affects, some are new products while others have existed in the store for a while. As far as individual product display is concerned: product is enabled, assigned to websites, assigned product to categories, product stock status is in stock, and verified product visibility. The categories effected are both new and old as well.
For an example:
Our Category 'TV Carts & Stands' has 11 products assigned (6 enabled / 5 disabled) and we see the 6 display on the website as we expect. Then we experience the issue with products 'falling off the website' and then this category becomes 11 products assigned (6 enabled / 5 disabled) but 7 products display on the front end. This extra configurable product does not have this category assigned to it and neither do the simple's underneath it. In order for us to correct this issue we must again run the indexer:reindex.
Community ticket that discusses the same issues we experience today back in 1.9:
https://community.magento.com/t5/Magento-1-x-Technical-Issues/Products-being-removed-from-Categories...
