What difference does it make whether you've got the ground plane or VDD plane adjacent the a signal containing high frequency harmonics? If you've got good decoupling, at AC the ground and power plane are the same thing since they're connected together with a very low AC impedance. I wouldn't worry about this too much, just put the +V/0V power planes in the middle on a four layer board and you shouldn't have any problems.
The recommendation to not to switch routing layers is from Howard Johnson's book High-Speed Digital Design (can't recommend that one enough!), where he recommends not to do that. The planes are still far enough to create quite big discontinuity in return path (remember that return current is mostly concentrated as near as the signal as it can, which is natural energy minimum for stored magnetic field = minimum inductance). Any imbalance of currents will manifest itself as common mode current, which shows up as EMI.
Adding a capacitor near the via, one improves the global VCC decoupling, and provides required return path. And it should be noted that the path of the return current is just as important as the signal current, however, it is usually unfortunately neglected. My measurements using a near-field probe shows that vias show up as high near-field points (not radiating, however). Situation changes if one has 6 or more layers. Then it is possible to change the signal on opposite side of same reference plane.
However, to be honest, it usually is not a big deal if there are no wide "fast" buses on board, like SDRAM or DDR. But it does not hurt to go "by the book" as much as possible, anyway (no added cost). I usually do not bother with extra decoupling caps, but I'll try to avoid swapping layers especially on clock traces.
Regards,
Janne