All your bases are belong to us
Attacks will have to be carried out based on known locations. The clans could pore over the map of their city, and check individual houses. Finding a residence that looks unoccupied, they can then question the locals about why it is empty. If it's not empty, then they've found a suspected location to nuke.
This may however lead to a lot of collateral due to false positives, or the other clan member may just not be home.
The attacker holds the advantage in this scenario though, as the base is known but not where the attack is coming from. This will lead to a long drawn out battle where each clans places of residence and bases of operations are slowly taken out.
EDIT: In case these clans are living in closed communities, this method just scales.
You'd then have to hire cartographers to look for anomalous villages. The settlements of the opposing clan would look perpetually "just been abandoned". The houses they live in, their fields, food set on the table, these things don't disappear. There will be random items constantly appearing and disappearing in the village, and once found the settlement would basically advertise itself to be the other clan's.
The searching process can also be augmented by getting known maps of the area as stated before and checking already marked villages.
Problem with this is, whichever clan is found first will be annihilated. The advantage lies completely with the attacker, and having no collateral to worry about, can proceed to completely raze the opposing village. The most likely tactic would be to set fire to the houses at night, taking maximum population, then burn the fields and food caches, and maybe set lesser traps on obvious exits to harry survivors.
Of course, that possibility might occur to the clans, and they'll modify their residences to suit defense.
- Scatter the clans into smaller villages.
- Set up efficient communication system between the villages. Horses will most likely be killed, probably poisoned, in the prelude to the raid. So there would have to be riderless runners. Hidden passes between the villages could be set up. Messenger birds could be trained (birds are much harder to target than horses I am assuming)
- Set up a constant warning system, with scouts hiding in the surrounding terrain with no obvious markers. If an attack happens in one village, the scouts immediately send message to the others to scatter.
- As they might have to run at a moments notice, packing might not be an option. The clans would probably contribute to hidden caches set up away from settlements that can be accessed by escaping refugees.