For any company that offers such services, I would do a search for feedback from past clients, to ensure there aren't an unusual amount of allegations of click fraud. 250,000 redirects is easy to obtain if they contract out to a botnet operator. Associated conversion rate data comparisons could be useful, if you can ensure they're not astroturf.
"One definite power that indie developers have--their competitive advantage against the big guys--is the power to lose money, and to be okay with losing money. Most of the time, a big game company just can't lose money, and that controls what they can do[...]" - Jonathan Blow