Depending on specific 'simple' cases this can be messy but effective.
The same deal happens for decision trees. (Axis parallel) Trees have a hard time fitting linear functions, requiring many modes. One can use essentially the same solution.
BTW very informative commentary. The things that you bring up really needed to be brought out.
Let me give a simple example. Say one wants to reflect 2D points along a line at 42 degrees. It's eminently doable in canonical basis but it's quite messy. Instead one can work off a different (rotated) basis such that that 42 degree line is now the x-axis. Now reflection is trivial. However the post reflection coordinates are in the new basis, so you invert the basis transformation to get your answer in the canonical basis.
For solving linear ODE with fixed coefficients you have a similiar situation where you transform to Laplace transform basis. In this basis the coefficient Matrix is a diagonal matrix, so it's trivial to solve. Then transform back (not always easy).
For de-noising tasks you need a basis where noise and signal have drastically different coefficients when expressed in such basis. Then it's easy to knock out the offending parts.
Harmonic functions are smooth and have the 'averaging' property. If you know beforehand that your desired unknown function is smooth in a similar way, Harmonic functions (for the corresponding smoothness measuring linear operator - the Laplacian operator) is indeed a very good choice.
As a counterexample if you want to denoise a photograph but retain edges, then Fourier is not very convenient because both edges as well as noise have 'high frequency' heavy representation. If you throw out high frequency components, the edge pixels are going to be collateral damage. The problem is that in this basis, edges and noise look the same. Shearlets, curvelets will do better here.
The "particular form" is important--if you don't know that then there is no reason for choosing x^10000 over x^5 (other than computational complexity). But there is also no reason for choosing x^5 over x^10000! Maybe that function really is flat and maybe it isn't. You really just don't know.
If you don't have anything too weird, Fourier is pretty much optimal in the limit--if a bit expensive to calculate. In addition, since you can "bandwidth limit" it, you can very easily control overfitting and oscillation. Even more, Fourier often reflects something about the underlying process (epicycles, for example, were correct--they were pointing at the fact that orbits were ellipses).
"Optimal" by what metric? Why is projecting on the Fourier basis "better" than projecting on a polynomial basis?
With respect to machine learning, probably the fact that Fourier is bounded and gives coherent (if completely random) results even very far from the interval of interest.
However, this is like saying that an O(n log n) algorithm is better than O(n^2). Sure, it's true in the limit, by the constant terms can be quite large and O(n^2) can remain better up to remarkably useful values of n.
As I pointed out, the advantage that polynomial basis generally has is that you can be accurate enough with lower powers that are much, much faster to calculate (we use matrices of linear equations precisely for that reason). Or, you can match a particular process because you know specifically that it follows some particular function (we know that road damage follows the fourth power of load--it would be counterproductive to model that with Fourier).
Using high powers for polynomial basis is almost always worse than any other choice.
If you know that some relationship is close to polynomial, obviously a polynomial basis is more suitable. E.g. a line performs terribly for a Fourier transformation.
>Using high powers for polynomial basis is almost always worse than any other choice.
For some value of "high", yes.