Ouch, I'm sorry to hear this! Indeed the tile stamps are stored globally instead of in the map, since the assumption is that they will be useful on many maps. For separating stamps of different kinds of maps, you can use multiple tile stamps folders.
Now, deleting the stamps does in fact delete their files and without backup there is no way to recover from that. The location depends on your operating system. On Windows, the default location is: