I think immortality can be a great game mechanic. It would encourage you to be creative on other conditions aside from death, depending on the reason for immortality. All you need is a strong gameplay focus that attaches to it. Whether it be exploration, rescue, creation; if it's fun enough, immortality will be an excellent compliment.