Generally the agencies that recruit on your behalf would rely on you to provide the criteria for selecting/screening participants, so the onus is really to make sure that you provide tasks that will allow the agencies to clearly distinguish real vs. fake customers/users.
That is not to say a fake user can't give you the same type of information that a user who is new or not familiar with your product or service, so perhaps it is not so important to make a clear distinction if your research is more explorative and the product is new.
Assuming that you have a good relationship with customers and maintain an up-to-date CRM, the participants should be drawn from it and then you wouldn't have this issue. Back let's say this isn't the case, then coming back to the question, the broad strategies that can be used would fall into the following categories:
A. Create a baseline for their knowledge and familiarity - if you are testing a new task or feature of the system, perhaps test their knowledge of the existing system. If they are a 'fake' customer or user then their level would be quite low (but perhaps put in a question about the frequency of their usage as a second check). This way you can then come back and eliminate responses for participants with the most suspicious scores if their responses are a bit difficult to interpret.
B. Use very specific terminology that are common for the customers of that company/product/service. If the participants don't understand or ask for clarification then there's a good chance that they are not actual customers.
C. Ask them about things that are known customer complaints, issues or pain points and their feelings/opinions about it. If they don't have any strong opinions or feelings (and their rating of the user experience or customer satisfaction doesn't match) then it should raise a flag for checking the authenticity of their status as a customer.
As for next steps, I would generally flag those participants and evaluate the rest of the responses first. If you have the numbers and significant results then you can discard those participants and don't worry about it. If you have low numbers and need to use or incorporate those data points/answers (perhaps look at changing your process for recruitment and testing first), then try to rank them on the likelihood of the participant not being a genuine customer and report this in your results. It is possible to try and verify their customer identity but it shouldn't normally be part of the process after you do the testing (it should be done before if you really want to).