Don't restrict the counterpart relation
Things are counterparts iff they are sufficiently similar to each other. They needn't be similar intrinsically: For example, in "Individuation by Acquaintance and by Stipulation" (§2), Lewis allows for counterparts that are similar in standing in a particular relation of acquaintance to some person. In fact, they needn't be similar at all: In On the Plurality of Worlds (§4.4), Lewis accepts that, speaking unrestrictedly, everything is an individual possibility for anything. However, in "Things qua Truthmakers" (§5), he denies that things could be counterparts by living in a world in which there are no unicorns. I wonder why. Lewis says that such a respect of similarity would be too extrinsic and strike us as too unimportant. But other eligible respects are extrinsic too, and what strikes us as important certainly depends on the relevant context. I can imagine theists who believe that there is a big difference between living in a world where there is a God and living a duplicate life in a Godless world. So in some special contexts, those of our counterparts who live in Godless worlds might be excluded as being too different. Conversely, an atheist might exclude counterparts that live in worlds with Gods a being too different.
I think there shouldn't be any general restrictions on counterpart relations. Rather, we should treat them like all other candidates for semantic values: The more natural, the more eligible. In ordinary contexts, counterparts by not living in a world with unicorns aren't very good candidates. But in certain special contexts, as when Lewis talks about cats-qua-unaccompanied-by-unicorns they may well be. Why not? That relation is gruesome, but at least it is finitely specifiable, unlike many more gruesome relations.
Restriction also appear odd if we consider the translation of counterpart theory into a theory of trans-world individuals. I take it that there is not a big difference between these two accounts (at least not in the interpretation of de re modality). Now the restriction on counterparts turns into a restriction on eligible referents for cross-world singular terms. But again, why shouldn't we have a term that refers to the mereological sum of all those cats that are unaccompanied by unicorns? In fact, I have just used such a term. So from the trans-world individuals perspective, there appears to be no problem with introducing "Long-qua-unaccompanied-by-unicorns" as another name for this mereological sum. Hence, given that there is not much difference between the two perspective, the respective counterpart relation should also be unproblematic.