This site has had similar questions about giving private information to recruiters but I haven't seen this particular case.
When I'm cold-called by an recruitment agency about a job, and I agree to be submitted, they often ask for birth month/date and the last four digits of my SSN. I'm never really comfortable giving it, but I usually do.
The agent who called today asked for the last four plus the FULL date of birth. (Most likely illegal.) I'd probably decline to give the info except for one thing: I gave it to this company two years ago, for better or worse.
The agency submitted me to a prestigious company that year and the next year, and I even got an interview out of it. So not only does this agency seem somewhat legitimate, but we may actually have a "relationship".
The new recruiter says my information is no longer in their database. Is there any reason I should not give this new guy the same information I gave his agency before?