I agree selection processes are indeed quite unique and proving any discrimination could be bumpy ground. If the ad was made and the agency were aware that only female applicants would be successful then their practice may well be questionable. I'd be concerned with the fact that you were able to apply and were rejected with that particular explanation - it shows a mis-placed honesty on behalf of the agency maybe as they should be able to equally support you & the cause for anti-discriminatory employment.
Wanting to keep your relationship on an even keel & help parents understand both genders can care equally for children, do you think the agency would be interested in campaign awareness & leaflet/information distribution to clients that promoted your services or male sitter services in general, safeguarding procedures, registered certificates/crb's or activities you offer to meet famillies prior to an arranged babysitting date?
As suggested discussing your concerns with them is a good way to go
Best wishes with it xx