I'm sorry to hear you both are seeing the same issue here. If your tags have more than one word in them, I'd recommend searching by just one word. If you were to delete/edit the tags that may feature the word you are trying to remove, this should also remove the older tags. For example, if your tag was 'kitchen accessories' and you wanted to remove it, but you also had a tag called "kitchen furniture", the kitchen accessories tag would still show as both tags share a common word.
If you did not want to continue editing your tags, you can also export your product list to a CSV, remove the tags on the CSV file and then reimport the full product list into the admin. If you wanted to test this out before you try this in your own admin, you can open a development store to use as a testing ground! Development stores are free to start and free to run, you'd only need to pay if you decided to start to run it as its own store (and began to take orders.) If you kept it as a testing ground though, it would not cost you anything. Many merchants do this to trial theme changes/navigation updates, etc without making any changes to their main store. In the development store, you can import a CSV file of your products as they are currently, then remove the vendor in the CSV and reimport there first to be sure this is a viable option for your store.
Let me know what you think!
Social Care | help.shopify.com