I wouldn't ever pay for an agency to do user testing, and it has nothing to do with money.

Your ideal tester is someone who cares enough about your product to use it.

I also wouldn't even start developing the product unless I had a decent sized list of people who really want it.

In which case, testing it is easy. Just ask those people to test drive your app during development. If your app solves a real problem they will happily do it for free since it solves their problem, but you could also give them perks like giving them 2 months of your service for free when it launches.

Your users will naturally give you feedback if things are broken, so that handles post-launch real world testing. Of course you'll want to supplement that with heaps of automated tests too.