There is absolutely no reason to comply with this.
If they want to ensure that your company doesn't send over former workers, the only thing they need is the name of the worker. They can check that against their database. If a match is found then your company and theirs can take a closer look at that specific individual.
If they want to ensure that the people your company sends over passes a background check, your company can either provide the results of the background checks or provide the necessary information to a known third party whose job it is to conduct such checks and have them do the research.
If they insist on this type of information, then you should counter that you need assurance that the data is properly secured. This "assurance" should include a list of everyone, including their SSN's, DOB, and address, who will have access to the data. You should also demand that they acknowledge legal liability plus a potential of huge financial damages via written contract in case it is found that this information was lost or stolen from their possession. This negotiation should be handled by the CEOs of both companies so that the seriousness of it is completely understood.
The point is, this isn't a normal request and there are likely many ways to accomplish whatever it is they think they need to.