How to place decoupling capacitor in four-layer PCB?
This is a complex problem to analyze and many parts of it only are important when you run into a problem at a specific frequency on a specific product that noone knows how to fix.

While this answer is sort of a side point, it addresses some assumptions.  We are talking about bypass caps which only concern is high frequency noise and not large power draws.  High frequency noise is best dealt with using monolithic ceramic caps (ESR less of a concern as it is just your minimum impedance achievable).  Larger power fluxes need bigger tantalum caps.  See the frequency performance here:



You can use the SFR (self resonant frequency) to your advantage.  If you have a problem with say a 1GHz clock leaking through, you can start by adding another bypass cap that is self-resonant a little higher than 1Ghz.  0402 10pF (from experience, not from the graph) are pretty self-resonant around 1Ghz.



However this is only part of the story.  What happens at higher frequencies?  The mounted inductance plays a role and that is where the layout also comes into play between the layers in the board.  For example a power layer and ground layer in the board with an SMD cap has the following mounted inductance loop model -- shown in red:



In an example of 2 planes (power/gnd) in FR4 you can see that at high frequencies even the mounting of the capacitor can make a big difference.  The black trace is without the cap.  The blue and red show two different mounting topologies that show different mounting inductances.



The anti-resonances can cause more problems at high rates.  And you might think you don't care about 1GHz+ noise, but the FCC might, and if you want clean edges on your digital 500Mhz signals, then you're going to need a lot of harmonics for that square wave.  For example a 100Mhz clock to have a 0.5nS rise time needs at least a 900Mhz harmonic.

So what about the package itself?  You've got output drivers, input pins, bonding wires, ground pins, power pins...(fyi ecb=pcb)



A full model would look something like this (including cross-coupling effects).  The cavity plane is where the die would be represented.  (Ignore the part with the Equivalent L+R for package Bypass Cap--that bit for a ic bonded with some on board bypass which isn't the case for this question).



Using microwave probes, a high frequency network analyzer and special TDR calibration fixtures the impact of the package both in terms of power/ground planes and cross coupling can be estimated.

Now on top of all that we have your question of where to put the cap.  I found a nice article by Howard Johnson who shows how to do a model of the system and how to analyze and measure it.  Here's an example layout and how to look at each part and optimize it.





Unfortunately the presentation doesn't go over your specific case of IC to vias or IC to cap to vias.  You could play with the model and see which provides more bypass but remember the cap effects, and the power to ground plane coupling.  My bet is if the chip is your noise source minimizing all inductance between the die and the cap would provide the best results assuming the vias for the cap are also near and symmetric like Case F.

EDIT:  It occurred to me that I should summarize all this info.  From the discussion you can see that there are many aspects of high frequency work that requires careful consideration:


type of capacitor chosen (package size, material and value)
the capacitance and anti-resonance of the Power-Ground plane itself
the capacitors mounting inductance (there are special SMD high frequency cap packages like ICD/X2Y)
digital designs need a surprising amount of high frequency harmonics
IC packaging type
lastly the layout


Case F optimizes the above layout model of the uC noise source by \$L_2=L_4=0\$ and \$L_1=L_3=minimum\$.

From the comments in the discussion with David about BGA's where placing the bypass on the back side of the board with vias can be ok and often the optimal choice. This is because even though \$L_2=L_4\ne0\$ you can really reduce \$L_1=L_3=small\$ and the overall solution is better than making long traces to the bypass cap without using vias.  In addition the BGA package style has less inductance which helps with bypassing.

In addition this model shows why the layout should be symmetrical as possible to make the bypassing cap most effective to reduce both ground bounce and supply spikes by keeping both ground paths and power paths as similar as possible.