I have gone to Lima 3 times in last 4 years(4th trip next month). It's best to call for a taxi(radio dispatched) if you are out and about in Lima and make sure to agree on price before hand. I agree with all the other comments below. You can walk up to the counter right after leaving customs( you will be mobbed after that, outside), I think verde taxi is one of the companies.