The paradox doesn't really exist if you introduce acceleration into it. A better example might be as follows: Imagine two twins, James and Mary, who are in deep space, each in their own space ship. They are both at the sampe point in space and then suddenly, without any noticeable acceleration, the begin to move away from each other at relativistic speeds. In James' frame he sees himself as stationary and believes that Mary's frame is becoming time dilated as she moves away from him. Likewise, Mary believes that she is stationary and that James is becoming time dilated as he moves away from her. This is the important part, that it is impossible tell whether James or Mary is the one who is really experiencing the physical effects of time dilation - it could be either of them. Suddenly, without any apparent acceleration they start to return towards each other (which doesn't imply that they are both moving) and then suddenly 'stop' in the same place. It is only once they meet up with each other and compare their clocks that they can know who was really travelling at the relativistic speed. It turns out that James has measured less time, hence it was he who sped off away from Mary and then travelled back towards her.
Now, if you consider the various effects that James experiences in travelling at a relativistic speed relative to Mary and then returning to her frame:
- Mass dilates (relative to the observer's frame) and then returns to 'normal' once you return to the observer's frame.
- Length contracts (relative to the observer's frame) parallel to the direction of motion and then returns to 'normal' once you return to the observer's frame.
- Time dilates (relative to the observer's frame) and then returns to 'normal' once you return to the observer's frame.
Note that none of the effects actually remain. Time dilation, as with the others, ceases to 'affect' James once he has returned to Mary's frame of reference. I don't know this for sure, but theoretically one doesn't actually notice all these effects as they occur. Within your frame, provided it is inertial, you notice no difference. This is why I emphasise the relative, observational nature of these effects - because it is only when measured by an observer in a different frame of reference that they become apparent.
This post is long enough as is but I'll finally get to the 'time dilation lingering' thing. If you replace James and Mary with twins and have their trips apart made quite long then we'll get that situation where one of them is middle aged but the other is looking grandpa-esque. Consider the following: if you have two things that are identical and, at a later time, you find that something is different about one of them. Why is it that you have noticed a difference? - it is because one of them has changed. Time is the agent of change. The rate at which time flows dictates, in part, the rate at which change can take place. As one twin travels at relativistic speeds then, relative to the stationary twin, the particles makign up their atoms slow down in their oscillations, their cells slow down accordingly and, as a result, their entire body system ages at a slower rate than the other twin. That time then has a lasting effect can be attributed to time being an agent of change which allows change/difference to occur/exist in the first place.
I hope that helps in some way.