So string theory is a developing theory with presumably different variants. What is the commonality among all these variants? What makes the next modification of a current string theory another string theory, as opposed to a completely new theory? More specifically, is there a general mathematical structure that is common to all the theories that are considered to be string theories?
In the 1980s, it was thought that there were several (well, five) variants of string theory or five string theories – type I, type IIA, type IIB, heterotic-E, and heterotic-O, much like the OP assumes. A hypothetical new addition to this set could be called "string theory" or "not string theory of a new type" and there would be a risk that the classification wouldn't be objective.
However, in the mid 1990s, it was realized that all these "theories" are exactly equivalent – they're expansions of the same theory around different points of the configuration space, around different classical solutions to the same equations, around different environments (determined by the expectation value of the dilaton i.e. the string coupling constant; and by the shape of compactified dimensions if any; and the addition of branes or orientifold planes).
It turned out that all variants are connected to the same "duality web". One may literally obtain the objects and interactions associated with (what used to be called) one variant of string theory if he starts with (what used to be called) another variant and changes the fields in agreement with the equations that govern them, or adds objects that the theory allows in the initial environment. And as hinted above, there's actually a sixth important limit, M-theory, only known since 1995, that doesn't contain any fundamental strings, has 11 spacetime dimensions and not just 10 as the other 5 string theories, but it still belongs to the same theory, string theory (or "string/M-theory") in the modern sense (or "theory formerly known as strings", as Duff says).
So there's only one theory and wherever we follow it on the configuration space, we find out that there exists a unique way how to "complete" its definition. There is no arbitrariness in the theory whatsoever. That doesn't mean that the theory only has one solution. Even among the vacuum solutions, it has many solutions. But the theory – defined by its equations (which we know at least locally in the vicinity of each point of the configuration space) – is completely unique and cannot be deformed or adjusted in any way (except for deformations that make it inconsistent).
It means that whatever laws of physics may be obtained by adjusting the actual fields or adding branes, strings, and particles to another configuration allowed by string theory must be called string theory, and whatever can't be obtained in this way isn't string theory.
There isn't any freedom to choose conventions or personal preferences when one decides what is string theory and what is not string theory. In this sense, string theory is analogous to the American continent. One may decide whether something is a part of it – whether it is continuously connected to Boston via land – even though we don't have the deepest defining equations that would determine the shape and properties of America everywhere. But no one will disagree that San Francisco and Austin belong to America while Havana and Moscow don't. It's analogous with string theory. The very verb "considered" in "what is considered" is misleading because it suggests that there's some freedom for conventions and opinions. There isn't any room for personal opinions here. All these things are cold hard facts.
As Dilaton has also correctly mentioned, the term "string theory" is historical and obsolete if taken literally. The theory was originally discovered in the "weakly coupled limits" by studying dynamics of strings but it was found to objectively contain lots of other objects (branes) and processes. We still use the same name "string theory" but it is comparably obsolete a term as if we were using Apaches' Extended Prairie for America. Such a name wouldn't honestly describe everything that is relevant for America.