The cursed city he was looking for isn't here.
It's more upsetting than it has any right to be. He's had an upsetting week, but still. Normally, looking for a cursed city and finding only bare dirt would be cause for celebration. Now, though... he had a goal in mind, a place he wanted to go, a thing he wanted to do, it wasn't by any stretch of the imagination a good goal but it was something, and instead of doing it he is wandering through this unmarked desolate wasteland because the cursed city he was looking for did not have the consideration to stay put.
He kicks a rock.
The rock flies through the air, tumbles, bounces, kicks up a puff of dust, and—vanishes?
Maybe the cursed city is still here.
He proceeds cautiously toward the rock's last known location.
Not, however, cautiously enough.
One moment he's taking a careful step forward; the next he's—a puff of dust. Too many pieces, separate but connected, each in a different place and moving in a different direction. Some of him is frozen and some of him is on fire and some of him is being crushed and some of him is exploding and none of him is okay.
He feels his sword die, and that's when he knows he's really in trouble.
It takes entirely too long for his immortality to figure out what the hell to do with this situation. At first it does the exact worst possible thing, and heals all the separate pieces in their separate places, keeping them intact enough to continue hurting but not reuniting them so they can stop. Eventually, though—after enough time that he loses all hope of counting it—something shifts, and he's whole again, lying facedown on cold hard rocky dirt. It's colder here, and the ground is uncomfortable, and he hasn't got any clothes because they all disintegrated, but he has a hard time caring about any of that next to the unimaginable bliss of not being in pain.
Maybe he will just... lie here for a while. It's not like he has any pressing engagements.