Is it possible to solve the Mountain Car reinforcement learning task with linear Q-Learning using the state as direct input?
I just found out the answer and it's actually pretty simple: while there is a good linear policy for the mountain car task, the value function itself is non-linear. 

The state space of this task is like a spiral, and there is no linear approximation possible even for a mediocre value function. If you increase the value for going right and reaching the top, going left will have the lowest values. This is why the car never reaches the top.

By applying a simple random projection and transforming the input space, it is possible to show that the task becomes linearly solvable (with a value-based method).