The answers on this thread so far all agree that "it depends". I thought it would be worth expanding on the loop area mentioned in some of the replies, because that's the crucial factor here.
It's all about loop area formed by the cap and the chip. Best to understand what loop area is, then you can pick the best compromise for any situation. There is no "just do it this way, always" solution I am afraid.
Loop area is the area formed by the path of the current flowing into the chip from the cap and the path of the current flowing out of the chip back to the cap. Let's call the in path V+ and the return path GND.
For most practical purposes up to say 1GHz frequencies you can just look at the top down loop area (i.e. just draw it on top of your pictures). At higher frequencies you might need to look at it in 3D.
Where you force the currents to flow in a traces, the path is clear - it's the lines of the traces. Where you allow one current to flow on a plane and the other is in traces, the path of the higher frequency currents on the plane will not follow the shortest path (which you might expect) - instead they try to follow the path taken by the current confined to traces. The lower frequency or DC on the plane will flow straight to the supply and miss out the decoupler completely, but these aren't interesting in the context of decoupler placement.
I've annotated your image with the (top view) loop area in each case.
The red solid lines are V+ flows from cap to chip & the red dotted line is the internal current flow through the chip.
The green lines are GND flows from chip to cap. Note for the left hand image the actual path taken by the green line from via to via will depend on frequency - the higher the frequency, the more extreme the divergence from the shortest path as the return current tries to follow the forward current.
The blue areas are loop area. You can see which one is better - it's the one with least blue.
Note I've cropped out the correct/incorrect text - it depends entirely on the application as to whether this is true or not - for certain applications the right hand solution might be good enough and might allow other routing advantages. It is unlikely to be the best solution, though.
I hope this helps.