Generally speaking I would advise to go with someone within your clients or your country and time zone. If your client is in India then fine but if they are in the UK then go with a UK company, if USA then with a USA company etc.
The other thing to be careful of is the language, you want it to be their first language so anything that is written is good and technically correct. Whilst I agree its tempting to save the money, you tend to get what you pay for in this business.
Whilst I have heard of good results from SEO companies based in India I have heard of many more where the site has nosed dived because of poor techniques. Is a gamble as is any outsourced SEO work but you can limit the risk and maybe damage by going for someone local that you can keep keep an eye on and check the work being done.
Just my 2 cents worth.
Good SERPS is great, Traffic however is even better