Raiding.

As a general rule in long-term, low-intensity conflicts like this, you don't target the other side individually, you target their stuff. This has a number of benefits: they need to put effort into getting new stuff (instead of fighting you), they needed that stuff to bring up the next generation of people to fight you (usually by "stuff" we're talking food, or other vital supplies), and of course you can get their stuff.

In this scenario, this has the added benefit that their stuff is not invisible. On the other hand, when you pick it up, it becomes invisible! Plenty of thieves would give their right arm for that trick. (Or somebody's right arm anyway.)

Even if you can't steal things, you could destroy or despoil them. If the enemy has cattle, maybe that's a little tricky to walk off with (although it's possible...) but it's still a big fat target.

On defense, you have fewer options. Stopping raiding parties is hard enough when they're totally visible! Aside from raiding them even harder, I'd expect them to specialize in physically-triggered traps. The clans aren't intangible, after all, so things like tripwires, pressure plates, pit traps, etc. are all fully functional. Big static defenses would also be valuable: a wall around your stuff that's difficult to scale, basically.

Attacking opposing camps has already been covered - aim for their belongings, not their (invisible) people. However defense is the important flip side.

Sound

• Trip wires with bells attached with give away an invaders position (this could be countered by making animals - perhaps a herd of deer - run towards the camp)


• Bells on doors - they're already close at this point but you know where they are


• A string of bells with tar (or some other sticky substance) on them, once they stick the enemy has to either stop to remove them and reveal their location or keep move slowly to avoid disturbing the bells

Other objects

• Objects that move easily (marbles, for example) would give away the movement of an enemy as they roll away from them - even if the initial object is invisible the others won't be


• 
  Watching for what isn't there: all those materials you mentioned (dust, oil, powder) would be invisible if they touched the enemy so the fact you can see those means your attacker isn't there

Using guard animals (dogs, etc)

• Their other senses are much better than a human's - using their reactions as an alarm would also be useful

Use the invisibility

• If any object you touch becomes invisible to them you could have razor wire at neck height and a watchman touching one (blunted) end, providing you with an invisible razor wire (this could also be used as an attach, sneak into the enemy camp and set traps like this)

Traps

• A hole in the ground or a snare trap will capture the enemy, you might not be able to see them (or your trap) but you'll know they're there because the trap was sprung

AoE

Area of Effect. Carpet Bombing. Indiscriminate widespread attacks.

You know roughly where the enemy is, but can't see them. So you attack the whole area.

Have your archers fire quickly and somewhat randomly. Heck, in open field war, archers didn't generally target opponents, they just fired quickly into the mass, expecting to hit something.

Even better, get your catapults and trebuchets, and instead of loading them with a single large rock, fill them with a number of head sized rocks. And depending on the situation (availability and possibility of out of control fires), mix in some incendiaries.

You don't have to hit specific people, so long as your barrage takes out some of them.

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.

A "dirty" solution for Day 1: Line your troops up, swords out, and have them march in a row while chopping and swinging wildly at fresh air and being very careful not to hit anything they can see.

Something a bit more refined for future engagements?

• Carefully trained, silent Bloodhounds, who can sniff out your invisible foes while remaining unseen by them.


• Small bells in a sticky/adhesive goop - thrown at your opponent, they turn invisible - but not inaudible!


• Train up assassins to pick out targets and avoid obstacles by sound. That wizard has provided you with a surplus of invisible ninja for your noble cause!

(Something that was not elaborated on - does the wizard tell the Clans? Or are they just pitched up, ready for battle, then wake the next morning to find their enemy is gone, but their tents remain. Scouts sneak in to investigate, then report back that they can still hear the enemy, but can't see them! How long until they realise that they are just as invisible to the enemy as the enemy are to them...)

I can't believe nobody suggested that yet:

BIOLOGICAL WARFARE

Bacteria and viruses don't care if you're visible or not, they just jump from person to person.

Throughout ages there were many ways to spread disease among the enemy. By throwing manure in their water supply you can have a nice cholera outbreak. Rats and other flea-ridden animals are wonderful for spreading bubonic plague. STDs, once introduced, are nearly impossible to eradicate.

As soon as a disease strike one side, the other can declare "temporary cease-fire for humanitarian reasons" and send them aid. Such aid can be, for instance, blankets previously used by smallpox victims.

Just be careful - that kind of tactics happens to backfire more often than not... which makes a good story.

Further reading: https://en.wikipedia.org/wiki/History_of_biological_warfare

Tactics would largely depend on the typical battle sizes and available technology level, so, without that, we are kind of stabbing in the dark.

At any rate, one thing invisible people leave is

Footprints

Especially for defensive and ambush positions, have the enemy approach over a wide stretch of sand, mud or similar, and have prepared some concentrated ranged fire - catapults, Greek fire or maybe some avalanche, depending on terrain. Mud and sand have the extra bonus of not requiring a lot of preparation between battles, and they work well with sound alarms described in other answers.

Blizzard

Not necessarily a blizzard, but either a snowfall, sandstorm, waterfall or saturation of area with a load of other small moving particles would show clearly the places where they can't go -- emptiness where there shouldn't be any shows up the invisible people.

Goose down

As an alternative, when you are already in a combat situation, you could have some sacks of slow-falling material -- goose down maybe, but a bit wet to make it slightly heavier(?) -- to throw over an area, with some bowshot or other way to split the sack while it is in air above where the enemy should be.

Fire, or maybe more opportunistically, water. Maybe ambush.

Presumably the invisibility doesn't extend to their housing. Look for the encampment of empty tents, village of empty huts, or whatever it is depending on your technological level, send in a bunch of soldiers in the middle of the night, and light up as much as you can.

Then either retreat before the smoke gives you away, or hang around and take advantage of the chaos to attack the 'holes running through the smoke and the spaces where water is pouring/shooting from.

Alternatively, if they're unwise enough to set up in a bad location geologically, dam a river and flood them out.

As for ambush, if you can figure out where they live, you wait until you can observe the effects of their actions. Well buckets dropping without anyone dropping them, unexplained disturbances at the riverside, farms tending themselves, livestock slaughtering itself. Then sneak up and swing a club or shoot an arrow where the person should be.

It's an interesting premise. It almost seems like the answer would itself be the story.

As others have suggested, a big part of it would involve the factions attacking each others' settlements. They could besiege each other, loot and burn each others' buildings etc.; and they could use their invisibility as a tactical advantage. For instance, Arbol assassins could lie in wait under every Byrond bed, and just stab a sword through the mattress as soon as they feel someone lie down.

They could also use proxies, of course (since you specify that third parties can see both clans). Presumably there would be a bidding war to control the loyalty of any highwaymen operating in the area, for example. You might end up with a Cold War-like situation where the main combatants don't attack each other directly so much as they arm and fund different sides in everyone else's conflicts.

Over time, I guess that it would make sense for the Arbols and Byronds to abandon their own settlements – which would be subject to constant guerrilla warfare – and hide themselves in "neutral" towns. There are all sorts of interesting possibilities where they could be living side by side without knowing it, kind of like the situation in China Miéville's The City and the City.

I think he offensive power of invisibility greatly outweigh defensive power. In the field it is almost impossible to intercept mobile force so the fight will take place in settlements and other key locations. Now the attacking side can scout the surroundings and layout (but not defense) freely and simply chose the moment, place and force to attack. The defender have to be ready all the time.

With millennia of bloody warfare and now without ability to see the enemies (and enemy civilians) it could get ugly quite fast - there would no reason to show any restraint, sneak in with small force and

• Poison the wells and spoil the food supply


• Set something on fire


• Apply weapons indiscriminately to beds and cradles

Now even if all attackers would get killed afterwards they usually inflict grave looses. And if attacking force is small then it have real chance to escape without retribution.

The defender have much more difficult task but can

• Use dummies and misdirection - like having multiple chambers (or even settlements) - some used - some filled with traps - and switch them regularly


• Try static defense - if they are able to limit approaches to very few round the clock monitored kill-zones they may have chance to get more favorable result. But the invisibility allows attacker to bring tools and helpers with impurity so I imagine anything short of underground bunker would allow the attackers to sneak around.

Finally I think one think could happen - after both sides settlements are savaged by unpunished foes both sides adapt nomadic lifestyle. With villages set up for night and torn down in the morning. That way the attackers would have to stumble upon settlement by chance and would have only very limited time to execute the attack. It would reduce intensity of the conflict and may with time turn the other side into invisible daemons from legends instead of real day to day threat.

Ninjas

As noted, actually killing people is hard work. Burning and stealing stuff is how you wipe a population out efficiently.

So you'll start out raiding. As each side is invisible to the other, you can do lots of theft and arson. If it extends to cards and mounts, it gets even worse.

This will do a lot of damage to both sides. Unaligned parties end up sweeping in and taking over territory destroyed by this invisible war.

In response, each side will seek to hide their settlements. They form hidden villages, and engage in warfare against their opponents. They'll test the limits of the "mercenaries" clauses (what if we don't pay them, but offer them plunder? What if we have no formal agreement, just a wink and a nod? What if we are their minions, and they pay us to be scouts for their army?)

Approaches to their settlements will be trapped in ways that reveal even invisible foes, while at the same time permitting defenders to move about undetected by attackers.

This situation either stabilizes, with both sides being secretive societies that hire themselves out as scouts to other powers, hoping to find where their foe is hiding. Or one is wiped out.

If one is wiped out, the other one's people are probably carried away as slaves. Their descendants spread over the world, each a blood-member of the clan. The surviving clan, now safe, may continue in its mercenary ways, banning out-marriage with prejudice. Over time the surviving intact clan finds that more and more of the regular world is incapable of seeing them.

They develop proxies, and work hard to spread the blood of their now-extinct foe. Those that remember the old clan are put to death, those that simply carry their blood are helped and encouraged to spread their seed. Every child they have is another nominal foe against whom these scouts are invisible.

One day they hope that every last human on Earth will not be able to see the Ninja-clan, and on that day they will be kings.

Attack engines akin to combine harvesters will happily mulch enemies - invisible or not. They have the benefit of taking out people, tents and other things above ground level without invoking a 'scorched Earth' effect on the land.

I believe the described conflict/vendetta is more of an "I want to see you bleed and pay for your faction's crimes!" type of thing.
So when they realize that they can't see the enemy "pay for it" and get satisfied, they could get this satisfaction by stealing the enemy's stuff (and mentioned above, "King of thieves" style), and/or sieging their villages/cities to the point of starvation, and/or using mass-destruction options compatible with their medieval tech (burning their places/things and hearing people scream in terror), but it probably is something that gives some feedback about the enemy suffering.

Duels are still possible, assuming both parties want to participate and make prior arrangements, probably via a third party. If they were in a small room or fenced enclosure like a boxing ring, they would still have to grope for each other, but contact would be frequent. It wouldn't be limited to one-on-one combat, either.

I once read about a ritual fight, between fictional native americans, in which they combatants' left wrists were tied together while they went at each other with knives. Again, it would require a third party and prior agreement, but mortal wounds would still be quite likely.

Negotiate peace among the tribes. A major change has occurred. Simply accept that major battle is not possible and attempt to make peace in accordance with the wizards wishes.

People not fighting and another plot arising is a great twist to a story. Especially if the original wizard could be found, or at least his journal. But in the meantime a greater evil emerges...

Okay but everyone seems to have forgotten the easiest answer: Hire someone to point out the enemies for you.

The clans are only invisible to eachother, so hiring an outsider will allow you to find the opposing clan easily. Plus you remain invisible so they will have a hard time defending. Most likely there will be a shift in fighting styles revolving around hired "spotters" who are linchpins in either sides offence. You can work several strategies around them, but the spotters are going to become the focus of the battles, either because they are pointing out enemies or being eliminated to cripple your opponents side.

Unless they count as mercenaries and get turned invisible? I was thinking of mercenaries being only direct combatants but spotters might count.

Trade War

Instead of physically attacking the opposite clan, both sides could switch to economical warfare. The members of both clans will likely engage in some form of economical activity in order to finance their standard of living and their war. So the clans could try to drive each other out of business in order to damn the other clan to a life in miserable poverty:

• Steal their customers by offering the same products for a lower price. Even if it means you have to sell at a loss.


• Drive their remaining customers away by slandering the other clan and their products.


• Buy out their suppliers to deny them their raw materials. When the suppliers don't want to sell or you lack the capital to monopolize the whole supply, sabotage the suppliers.


• Poach their best employees, even if you don't actually have anything for them to do.


• Find out if they do anything illegal and rat them out to the legal authorities.


• Steal their business secrets. If you find some secrets you can't use yourself, give them to anyone who can, just to harm them.


• Force others to take sides. Do you have any business partners who depend on you? Tell them you won't make business with them anymore if they also make any form of business with the other clan.

The only downside: You always know that even if you ruin them completely, you won't ever have the gratification of seeing them beg for food.

Dogs.

The clans are invisible to new pets they've gotten after the wizard left right? Have dogs, crows, and other animals identify enemy clansmen. Then all the clansmen need to do is "disagree physically and energetically without safety in mind"; the clansmen just need to attack whatever the dogs identify.

This is pretty similar to how Law enforcement uses drug dogs. Just gotta get dogs to identify people you can't see. Should be easy enough given that you know where your enemies used to live.

paintball

Go to the enemy's camp and hold-on to your favorite position.
Fire a paintball. Best shot is done with a shooting squad shooting at a wide angle, or few shooters with cluster paintballs. The paint will do its task even on the ground: each enemy troop stepping on it will leave footprints.

Even if the spell does not allow to see anything on their body (shield, arm, paint, etc) you have two tell-tale signs:

• the path of the paintball is disrupted when it hits the target




• the footsteps will once again be visible when they are left on the ground (enemy no longer carries it).

Now that the paintball has done its task, it's not time for laughing, it's time to pull your guns...