Is there a "flaw" in the backpropagation algorithm?
There's no paradox.  This is not a flaw.  Nothing is going wrong here.  In both examples, you're making steady progress: the output steadily gets (monotonically) closer and closer to the target.

Looking at individual weights (like w1 or w2), there's no reason to expect them to vary monotonically during the learning process.  If we perfect foresight and we know what the final optimal values of the weights are, we'd know whether each weight needs to increase or decrease -- but we don't.

Remember that backpropagation is just gradient descent, used to minimize some loss function.  Gradient descent is a local method for optimization: it makes a locally greedy step.  It has no global knowledge and as a result if you look at any single weight (any single coordinate), it won't necessarily vary monotonically: it might increase and then decrease, for instance.

Can you improve on backpropagation?  Yes, you can.  A large part of the success of deep learning is that researchers have found improvements to gradient descent for training neural networks (e.g., learning rate, momentum, and more).  Nonetheless, they're still optimization methods that work by taking a locally optimal step, and so they can be subject to overshoot and to phenomena such as you noticed.  Multidimensional optimization is hard.  You're going to see this kind of thing happen in pretty much any iterative method for optimization.

Bottom line: This isn't a flaw, this is only to be expected, given the difficulty of multidimensional optimization.  You still get to optimal values in the end, and that's almost-miraculous in its own right -- you should be glad for that and not worry too much about the fact that it takes longer to get there than if we already knew what the optimal solution was before we began.