There are numerous problems with the picture painted above, but for the purposes of parsimony and brevity I'll stick to just one. There is something missing from all of the above examples as well as all of the logic trails used to explain why these smaller navies with high-tech, fast-moving, lethal weapons can make a go of it against a bigger one.
Information.
Cruise missiles are useless if you don't know where your target is. They're only slightly less useless if you know where it is when it's three or four hundred miles away, but it's moving at twenty or thirty knots in an unknown direction - even if the missile travels at the speed of sound. Naval combat isn't, foremost, about how to kill the other guy - it's about how to find the other guy. If one side (the CVBG) has sea-search aircraft, dispersed escorts with search systems, and (let's say) oceanographic surveillance satellite systems, it is going to be very hard for the Sovremennys to get close enough to find the battle group. The carrier itself, in any case, is likely to be under EMCON anyhow, leaving the electronic noisemaking to the escorts. If this is true, it will be even more difficult to target the carrier itself, since you won't be sure where in the battle group formation the deck is.
The cruise missile still needs to be able to see the target when it arrives and enters terminal phase. If it uses active radar, it makes itself a target for both interdiction and countermeasures; if it uses passive sensors, the range at which it can 'see' its target is sharply limited, making accurate and timely information even more critical.
Shkval certainly does sound impressive. However, it's been around for quite a while, and it isn't really in widespread use, despite what you might think. The nature of the weapon limits its utility to one thing, really; single-shot, highly-lethal attacks on high-value targets. This means that if you want to bring down an aircraft carrier with one, you're going to pretty much need to put a nuclear warhead on it. One of the weaknesses of the above arguments is that they fail to make any differentiation between nuclear and non-nuclear naval warfare. To date, there hasn't ever been nuclear naval combat, and while this may or may not hold true in future, it is quite certain that in those cases, while a Shkval can then take out a carrier and perhaps a few of its escorts, it will be much much harder for the launching submarine to get close when nuclear-tipped Subroc and depth charges are available.
Cruise missiles such as the Moskit described above certainly can be lethal. However, they will be coming up against a system (the Aegis) which is designed specifically to defend against swarms of their brethren. As for Aegis being 'unable to lock on to the Moskit,' I would note that Aegis radars and missiles are, with some minor modifications, able to engage targets as diverse as incoming medium and short-range ballistic missiles (much, much faster) and cruise missiles and/or aircraft up to 100 nautical miles from the launcher (which may or may not be colocated with the target; in a CVBG there are usually launchers on escorts ringing the target up to 50 nautical miles away). Coupled with a radar which can detect and track targets up to at least 200 nautical miles distance (in some cases, much more) the cruise missile's chances begin to look less than stellar. The Aegis is not, as implied above, limited to Phalanx CIWS systems and decoys - the Standard SM2-ER missile is designed to attack cruise missiles and aircraft up to 100 nautical miles away.
Finally, while it is true that the weapons are much cheaper than their targets, recall that the owner of the targets (the U.S. Navy, say) has those same weapons - and in much greater numbers, usually, and doesn't mind throwing large numbers of them to protect their high-value assets. Comparing the dollar value of the weapon and the target is pointless; instead, compare the number of weapons it will likely take to complete the mission with the number you have in the stockpile when war breaks out.
This is not to claim that in fact none of the recent advances in weapon technology have any effect on the standoff. However, given the extremely expensive nature of weapons design and research, and, more importantly, research and design of countermeasures, the larger, richer nations still retain a most significant advantage.