(disclaimer: I have some assumption about your sitation, but i cant comment to your question for clarification)
Recruit a representative pool from all your client's users
This method doesn't need collaboration from your client. You will be in control, but needs more effort for the same sample size and quality.
Analyze the user base size of the apps where your service is present
Weight the recruitment effort according to the distribution
Define a representative pool for email surveys.
Design a survey. Make some low sample size pilots, for pivoting, optimizing.
I guess the completion rate will be in between 10-30%. Of course, you can use motivation, like amazon coupons.
Collaboration with your most representative clients
- List all your clients and try to pick some, who represents the variety of your costumers the most.
- Write some template emails to your clients market/UX researchers, asking them about their surveying routines (if any)
Maybe the representative ones already surveying, so you will have the channel.
And maybe they will be helpful and implement a survey for you.
- Try to convince them/their bosses with a short pitch about why its good to their product if your service will work better, thanks to a better understanding of your users.
And the last chance:
- The same pitch, to your boss, why he needs to give some discount to your client, for winning the cooperation :D
Expensive but simple solution
- Outsource recruiting, create a screener and see if the researcher agency has enough potential participants.