The problem with that is - how to do you KNOW anyone ever actually planted a tree with your money? I am a bit of a pessimist admittedly but I can imagine the tree company counting a few trees twice and three times and pocketing the difference. The truth might never come out.
And furthermore - the tree might represent some tiny percentage of the pollution a flight caused. What about the environmental cost of that big airport in some location for 100 years with the heat/a-c running, all those lights, etc?
If you assume everyone's a liar, how do you participate in the modern economy at all?
Oversight does exist. If you're concerned about a specific claim being valid, there's usually a way to investigate.
The whole carbon-credit industry is questionable, and the tree-planting stuff is particularly sketchy. The David Suzuki Foundation, which generally supports these carbon-exchange type things, makes special mention of that on their website. For the carbon credits to be legitimate, they should be completely new, something that wouldn't have happened without the program (ie, you shouldn't claim credit for a forest already growing) and the credits shouldn't be counted more than once. This is apparently quite difficult to guarantee.
As an example of how these sorts of programs fail: outside of Vancouver, where I live, a piece of land with mature tree cover was logged so it could be turned into money via carbon credit. Since it needed to be 'new' trees, they logged the old ones.
The fact that saplings fix very little carbon compared with new trees and will not catch up in volume for a couple decades didn't matter to the third party who certified their credits. This was a net loss of carbon fixation, and what's worse, the trees that were planted to 'balance' someone's flight will take 60 years to do it. Meanwhile, the extra C02 is around for decades, along with an additional deposit each and every year after that, by someone who now feels okay about flying because they're 'carbon neutral', thanks to the tree-planting program.
And that is assuming the tree is actually allowed to grow, which is quite a stretch. Think anyone is going to care thirty years from now if someone wants that land for a mall and the business that sold the credits is gone?