Since there are so many different combinations you can probably make this arbitrarily complex. Then 7/8 of the feature are the guessing of the category. The question is whether it is worth it.
You could search all registered packages that start with the same stem for subclasses of TestCase. That may introduce some unwanted dependency between trunk packages, so you may want to stick to categories rather than packages instead. You may program for the known patterns, so add your *Tests-* pattern to the list. Which one comes next? If there is no existing test category with the stem, which of the conventions do you choose?
Per KISS I would stick to just one convention, which can also be the one you mentioned rather than the one I implemented. Changing the category of the class afterwards should be easy enough.