you cannot be destroyed

In the sense that your mind and magic will hang around, yes. But your material form can still be destroyed, and material destruction of a Horcrux will destroy its ability to anchor the spirit.

So, if two people are mutual Horcruxen, you can still kill person 1, at which point s/he will become a disembodied spirit dependent on person 2, but will cease to be an effective horcrux for person 2. You can then kill person 2, which will permanently kill both of them.

All you really achieve with mutual Horcruxen is to make your Horcrux portable and fragile (subject to illness, aging, accident, etc).