[Gurthang]

I think what Arwen gave up was not necessarily immortality as we think of it.

We think of immortality as living forever, being invincible, incapable of dying. But Elvish immortalness was not such, because Elves could and did die. The reason they are immortal is that they won't die unless they are killed by something and even then their spirits simply go to Valinor. They still exist in the same world.

Men's death is different, for they leave the world, and go somewhere else.

So when Arwen gives up immortality, I think she was giving up staying in Arda when she died. I would think she could still live forever in Middle-Earth, since her Elvish body wouldn't age(as Gothmog points out), but when something did kill her, she would leave the Circles of the World, unlike her Elvish family.