I flew AA from the U.S. to LIM and back in May, with flights on LAN lim-CUZ-LIM. We had to pay the departure tax on the flights to CUZ and back, but not on the departure for the U.S. (as mentioned above, we got a sticker on the boarding passes).

I was not impressed with the check-in counter agent's command of English, however. My wife's passport has a typed endorsement changing her name to reflect her married name. I told the agent when we checked in. I don't think she understood me, because she SSSSed my wife on our second and third segments (but not on the first one, LIM-MIA). I'm pretty sure the SSSS was for name not matching name on picture ID, because the agent did not understand when I told her where to look.

It is possible that the OP and the agent miscommunicated. The departure tax should be in the ticket price.