If you can tolerate some error, a bloom filter might work. Both parties make their own bloom filter and send the results to the other party. The good part is

If you can tolerate some error, a bloom filter might work. Both parties make their own bloom filter and send the results to the other party. The good part is no personal data goes inside. I mean, you cannot tell beforehand if someone is a customer until you try to store their data into the filter. Bad news: bloom filters have erros. So, before doing this better guess the monetary value of the error.