Adding a new Item does get indexed
When I add a new item on content tree, it does not seem to appear on index on both master and web. Even after publish, I see the item on web database, but, I do not see this item on Index and neither on search results until I rebuild my index. I am using OOTB configuration for Index Update strategies which should typically be SyncMaster and Publish End Sync. FYI, when I update an existing item with a new field value for example, everything works great the changed value shows up on Index and listing fine. We obviously want to resolve this problem as content authors would not want to rebuild their index every time they add a new item
Something is still strange in the behavior you are describing, because if turning off and on the Live Indexing solved the issue, the Rebuild of the index should not have worked either.
Regardless, when using multiple Sitecore instances on a single Coveo Enterprise Search server, you may reach a point where the number of Sitecore sources exceeds the pre-configured amount of concurrent indexing connectors. This will result in various indexing issues, for instance some items not getting indexed. Manually toggling the Live Indexing will reactivate the connector momentarily, but other sources may still be impacted.
Coveo has an article to explain and solve the given case the right way: https://support.coveo.com/s/article/Coveo-for-Sitecore-indexes-refuses-to-get-created-in-a-Sitecore-multi-site-setup