What would happen if two wizards made each other a Horcrux? Would they be invincible? How would you kill one of them?
A horcrux does not prevent a wizard from being destroyed.
Voldemort lost his flesh and blood body when his Killing Curse rebounded on him. The only thing his Horcruxes did for him was anchor his spirit, allowing him to return once he recreated a body.
So in the unlikely case of two wizards being Horcruxes for each other, once any one was similarly destroyed, that would also destroy any Horcrux. There would be no body for the "foreign" soul to reside in. Removing both wizards from their body would be enough to send them both beyond the veil, since neither can act as an anchor for the other while they're merely spirits themselves.
No, they wouldn’t be invincible.
Horcruxes can be destroyed, and putting one in another wizard won’t save it from destruction. The pieces of soul in Horcruxes are dependent on the objects they’re encased in. One in a living being depends on that being staying alive and in its body - killing Nagini also killed the piece of the Dark Lord’s soul in her.
“But my point is that whatever happens to your body, your soul will survive, untouched,’ said Hermione. ‘But it’s the other way round with a Horcrux. The fragment of soul inside it depends on its container, its enchanted body, for survival. It can’t exist without it.”
- Harry Potter and the Deathly Hallows, Chapter 6 (The Ghoul in Pyjamas)
Wizards who have Horcruxes can’t be killed, but they can be ripped from their bodies by things that would kill them, like the Dark Lord was when hit by the Killing Curse.
“I was ripped from my body, I was less than spirit, less than the meanest ghost … but still, I was alive. What I was, even I do not know … I, who have gone further than anybody along the path that leads to immortality. You know my goal – to conquer death. And now, I was tested, and it appeared that one or more of my experiments had worked … for I had not been killed, though the curse should have done it.”
- Harry Potter and the Goblet of Fire, Chapter 33 (The Death Eaters)
If two wizards each make each other a Horcrux, the first time that one is ripped from their body, the other’s Horcrux would be destroyed as it can’t live without its enchanted body, which in this case would be the body of the first wizard. Then, the first wizard would be bodiless, and the second would have no Horcruxes, so could be killed. Killing the second wizard would be then relatively easy, and killing them would then destroy the first wizard’s Horcrux, leaving them mortal. Though it’s a bit complex to kill both, it’s nowhere near impossible - killing the Dark Lord required even more steps, but was still done.