I'm sorry to say you were scammed, and the charge was not legitimate.
While many airports charge departure tax/service charge, the majority of airports nowadays include this charge into the ticket price.
There are still ones which do not, and charge the tax from passengers (their usual rationale is that some categories of passengers are tax exempt). I flew through a number of those in South Asia. However in this case you are issued a receipt or a stub, and it is checked when you go through security or immigration (to make sure you indeed paid the tax). Since you didn't mention any checks, this is not the case.
Now what to do. It is unlikely you wouldwill get any money back (the guide is likely to say that this didn't happen and its your word against his). However it still makes sense to notify the tour firm and authorities, because:
The tour company needs to know about your complainscomplaints against the guide. While it is your word against his, it might be possible that other people complained about him before, and a series of complainscomplaints is likely to have consequences.
Complaining to local authorities, such as those regulating tour companies, works the same way. If the tour company decides to do nothing, but there are complainscomplaints against the company, the series of complainscomplaints is also likely to have consequences, such as revocation of license.