This Is Why We Can't Have Nice Things
If immortals themselves can't be usefully harmed directly, and if you're tired of the "what if we put them through a wood chipper over and over again..." shtick, let's consider the next big issue: if these immortals are like humans, they care for things other than themselves.
Pets, plants, houses, gardens, gifts they were given (or are working on to give to someone else), monuments, relics, symbols, etc. These things are all anything but immortal, and just as humans can care for things they know won't last their whole life (pets with short life spans, flowers, even other mortal humans), these people should care about something.
Sadly, in a state of war, these things become the primary objectives. If you can't destroy your enemy, destroy what your enemy cares about.
Pillaging, Razing, Raping, and Looting
Your immortals should tend to want to defend the things they care about, rather than merely themselves. Some immortals will just want to watch the world burn, having given up on caring for anything impermanent and inferior, while others will likely come to hold the idea that just because something won't last forever is no reason to let it be taken away prematurely.
Greed, jealous, and envy should also still exist. Why do those people get gold-plated crowns and comfy chairs - what, do they think they are better than us?
Everything has a season and a time
We can enjoy it while it lasts, grieve, and then move on to the next experience, and your immortals should understand that - again, all the more reason to develop, build, and protect what you care about. Some will want to hurt others by taking away these things, and some will fight to protect what they have.
Get them before they get us
Just as humans have problems with pre-emptive attacks, your immortals should too. Sure, the Others SAY their forge is for creating building materials for their city, but that "column" sure looks like a potential battering ram to me! And are those hammers for building, or war hammers?
Your societies may tend to think the other guy is working on siege weapons (weapons of mass destruction), and if they have the facilities they need to build weapons of war then you'd better have some of your own too. Fear leads to arms races, and arms races lead into escalating conflict - and war.
Siege Weapons Are The New Primary Weapon
Given all the above, why should immortals care about pointy sticks? Sure you can slow down the others, and that will have some value (hacking off legs, pinning them in place temporarily with a big spear, etc), but that's just a means to the new end - destroying stuff.
If the goal of the combat moves from "killing and maiming" to "breaking and burning", the weapons they choose and how they conduct warfare should change more dramatically. Historically siege weapons were not so extensively used for this reason, but with the focus now being on 'things' instead of people siege warfare should see a new golden age!
I imagine hammers, ballistae, flaming weapons (arrows, pots, etc), catapults/trebuchet, hammers, and "area denial" weapons (raining arrows/rocks/shards/fire/caltrops/spikes) will be thrust to the center of the action. You'll still need cutting weapons, but you also need a new strategy: how are you going to make off with the goods in a hurry?
I imagine speed, mobility, and carrying capacity will be a big concern. What good is raiding the enemy city if you can't carry off their giant golden phallic objects? You need wagons, maybe horses (uh oh, those aren't immortal...), and probably other developments that were not the norm in the middle ages.
Cue Gunfire and Explosions
Remember, too, that cannons and gunpowder are achievable in the middle ages - and in Europe this was not so important partly because of how war was fought. But if hurling a big iron ball hundreds of yards, or making things explode in flames, suddenly becomes more important than accurately hitting individual people, why wouldn't they emphasize it's development much more than historically was the case (and thus more like some of the advancements made in China for other reasons)?
Rockets, incendiaries, the rediscovery of Greek Fire (or it never having been forgotten), boom boom boom! All are suddenly very attractive to immortals! Armor and long bows - boooring, let's blow some stuff up!
Maybe they can just use foul language
With physical necessity out of the way, things are going to be even more heavily culturally and emotionally influenced than they are now. If war isn't about killing, it might very well commonly be about sending a message, proving a point, taking the other guy down a few pegs, proving your groups superiority, and so on.
Suddenly insults, foul language, and other such 'psychological warfare' can take on new meaning. If sticks and stones breaking your bones can't hurt you, maybe words will!
Now go away, before I taunt you a second time!