It's not your task to have the test company doing its job. In fact, you have practically no power on changing how they do things. If the customer wants to use this tester, you should accept it and simply bill all the hours spent digging through those absurd bugs reports.
You then present the results to the customer: 500 bugs created, median time spent per bug: 4 hours (at $XX rate), 430 bugs turned out not to be bugs at all...
I agree admit that -even if it means extending the project- it's still highly depressing for the developers to go through that.
It would be tempting to bill differently duplicates or invalid bugs (those that the testing company should not have opened), while actual bugs (things your company did wrong) could be done at a lower one. However, that would create a perverse incentive for you to close as Invalid/Duplicated (and for them to discuss that the duplicate is slightly different than the other bug).
So rather than going such route, given that your main problem is the extremely low quality of their bug reports, I recommend that you split the procedure of dealing with their bugs.
When you receive a bug report, it would first go through an acceptance phase, where a team from your company (best results would be by people specialized on testing, but it could also be former by the developers, or a rotating subset) would have to validate it locally according to their instructions. This is something you always need, but I would make sure to make it explicit (and perhaps billed at an higher rate than the rate of fixing them once you validate it). If the testing copany does a good job, with clear bug reports, validating a bug should take just a few minutes, whereas if they are performing as bad as you describe, all extra time for that would be clearly accountable for this. (The customer might then recover the expense by penalizing the test company for the extra time your people had to spent due to bad invalid bugs... that's up to them)
You would be confining the issue on this step, whose output would be clear actionable bug reports for your team. The result of this cleanup would also provide valuable feedback for the testing company (in case they care), showing which the way in which bugs should have been described, those that should not have been created, etc. and is a way to 'sell' it to the customer.
However, regarding the request to proposing a strategy to improve their test factory work, simply don't. You might be able to help a willing company improve their procedures, but this one seems a lost cause. And you really can't force them to improve (eg. while you might want as first step that all of those working on your project knew English, so they can actually understand what they must test, you wouldn't be able to hire or fire anyone).
If you accept this request, and things don't improve, then it could somehow be your problem that they didn't improve ("your strategy is clearly at fault").
IMHO the approach you should take is to offer a quote of the testing task performed by your company. That would be a different contract, performed by a different team than the developer one, by professional testers. And unlike trying to improve that foreign tester factory, there your company would be able to vouch for the quality of their results.
Surely, contracting your company would be more expensive at face value, but after taking the into account all the extra effort (and thus money) that their careless approach requires, it is probably worth it. Moreover, I am sure these "quality testers" would be able to uncover bugs that those foreign testers that even had problems reading the specs would simply be unable to.
Obviously, if your customer nonetheless wants to continue working with that company rather than taking your quote, it's up for them.