It is best to think of the Filter Menu as a collection based filter, it not a tag based filter, even though it uses tags. With that in mind, we always want to make sure our products are in the right collection first, before we start adding any tags.
What is happening is that the source of the filters is the collection, not the tags. The Filter Menu app will try to keep the collection and the tags in sync, so if you manually add a tag it will see that the newly tagged product is not in the collection and will remove it.
Believe it or not this is a good thing though, so bear with us. It is often much easier to manage your collections with rules rather than having to manually apply many tags to each of the products.
So at the end of all this, what you need to do if you want to add a product to a filter is to either:
1) Adjust the product properties such that it appears in your desired collection
2) Adjust the collection rules, or if it is a custom collection add the product to the collection.
For example if you have a product that is having the tags overwritten, check to see if it is in the matching collection for that tag. It won't be in the collection, so try edit the product or collection so that it is added to the collection.
Let's say we have a tag of 'shoes' that is being removed, check the 'Shoes' collection first. Notice that the product is not in the 'Shoes' collection, because the Shoes collection has a rule of 'Product Type equals Shoes'. We can check the product and notice it has a Product Type of 'Boots'. We can now either change Boots to Shoes, or change the collection to also include Boots.
Also check to make sure your new tag does not match the rule set in the Variant Tagger, if you have that enabled. This will have the same effect of removing any tags you add, as it tries to keep your variants and the tags in sync.
Here is also a video guide: