Partial immortality is the most common form of immortality in fiction and why not?
Immortality tends to be more of a curse in mythology. Cursed immortals tend to have a very specific way they can die but otherwise will regenerate or be indestructable.
You might want to consider changing what bypasses the immortals regeneration. Maybe change it to lawful weapons (inevibility of death) or cold (slows down cell activity, thus stopping regeneration). Or maybe make them vulnerable to a divinely ordaned substance if these immortals are supposed to be campaign setting specific. Fire and acid seems too troll-like to me.