My entry on the Russian defense minister claim about multipurpose submarines' carrying tactical nuclear weapons ended with a question mark - I doubted that they do carry them, but the evidence was not entirely conclusive. I think I can remove the question mark now and say that the evidence, while still somewhat inconclusive, strongly suggests that there are no nuclear weapons on Russian multipurpose submarines.
Unfortunately, the State Department balked at releasing the cruise missile declarations - they said that they would need Russia's consent to do so. But they confirmed that these declarations exist and the latest exchange took place in December 2005. I am quite positive that if these contained anything other than zeros we would have heard about it then. In addition to that, people who know the situation in the Russian Navy assured me that Russia strictly follows its 1991-1992 obligations (panicky claims by some experts notwithstanding).
What's interesting is that Russia seems to reserve the right to deploy nuclear SLCMs during a "threatening period". Which is not really a good policy - should we find ourselves in a period like that, the very fact of deploying nuclear weapon on ships would only make the tensions worse. Whatever value these cruise missiles are believed to have, it is not worth the increased risk.