The simple past, as in "I saw her" or "Did you see her?", generally implies a specific time, or inside a specific time-range that ends before the present. For example, I might say, "I was looking for her all of yesterday, but I didn't see her." This means that I didn't see her yesterday — but it doesn't say anything about whether I've seen her today. The following sentence could easily be, "So I guess she must have left town; I don't know if I'll ever see her again", or it could just as easily be, "But then I ran into her five times today, when it was already too late to invite her."
By contrast, the present perfect, as in "I've seen her" or "Have you seen her?", implies that the time-range of interest ends at the present. For example, one might say "I've been looking for her all day, but I haven't seen her."
It is possible to have two sentences that are identical except for this distinction, in which case the verb form conveys an important nuance of meaning. "I didn't see her today" implies that "today" has finished in some way — perhaps she is a coworker, and what I mean is that I didn't see her at work today, even if it's possible that I might run into her at the grocery store in the evening — whereas "I haven't seen her today" implies that there's still a chance that I will see her later today.
In your example, however, I would say that only "I'm looking for Paula. Have you seen her?" is acceptable. I cannot think of a context where "I'm looking for Paula. Did you see her?" would make sense. "Did you see her?" implies that you are referring to some specific past time or some specific past time-range; but since it doesn't explicitly indicate the time-range, that must be inferred from context. The problem is that the previous sentence, "I'm looking for Paula", implies that the time-range of interest is now, and the "did" version must end before now, so it's not compatible. As a result, saying "I'm looking for Paula. Did you see her?" makes about as much sense as "I'm looking for her. Have you seen him?" — the second part must be referring back to something, but it clearly can't be referring back to the first part, so the whole thing comes out sounding like gibberish.
Present perfect stands for completed actions where the exact time of the action isn't important. Hence when you use it, this tense doesn't answer when exactly the event happened.
— Have you ever been to Paris? —
— Yes, I've been there. (It doesn't imply when.)
Past simple stands for actions that happened in the past at a specific point.
— When did you go to France?
— I went to France three weeks ago. (It shows the point when this happened.)
Best Answer
Either one is possible.
The first example is still correct even though Amy Winehouse is dead, because it asks about the hearer's experience in life.