That’s quite an interesting idea. IIRC, an informal organization dubbed the NATO-Russia Council was set up in the early 1990s to try to foster a closer working relationship between the two, and I know Tom Clancy latched on to the idea and had Russia join NATO sometime in the mid-1990s in the Ryanverse. However, I think that the biggest obstacle to be overcome is the fact that, in order for Russia to join NATO, NATO itself would have to undergo a rather extensive reform process in which its internal bureaucracy, power-sharing arrangements, areas of deployment, even its fundamental mission would have to be reevaluated. Unfortunately, it would be safe to say that the 1990s were not a period in which Western statesmen were contemplating extensive reform proposals. In the United States at least, there seemed to be a drive towards disassembling most of the military and state apparatus that had been built up to fight the Cold War. There were lots of strange proposals floating around, stuff like refocusing the CIA on economic warfare while phasing out ground agents, of turning the military into a tiny technologically-overstocked precision-instrument that would swoop down anywhere in the world in a day, fight, and disappear by daybreak. While the government and foreign policy inherited from the 1980s did have a lot of deadwood that sorely needed clearing out, generally speaking there wasn’t much of a will to actively remake the world. Heck, Washington’s sole policy regarding Russia was “don’t let Yeltsin fall,” regardless of Yeltsin’s own competence or of the well-being of Russia itself.
At the same time, I don’t think that much enthusiasm existed for the project in Russia. After all, while the Russian Federation was founded as a consciously ethnic Russian enterprise, the nation still has a legacy of multinational imperialism that cannot really be avoided or denounced. At its most metaphysical, “Russia” has encompassed Belarus and Ukraine as well as Russia, and ethnic Russians themselves are spread all across the CIS. To join NATO would be to abandon this traditional outlook, and to just accept the post-1991 order as something to be cast in stone, with Russia forever stuffed within its new shrunken borders. While the Russian state and the Russian people generally don’t care much for each other, I would say that this is an issue where their opinions actually coincide. Also, having Russia join NATO would raise the possibility that American and European soldiers would be dispatched to the CIS states, or even Russia itself, for peacekeeping duties, and I can’t imagine any Russian politician (or an American one, for that matter) worth his salt condoning such an act. Just look at the stink that’s been raised over Kosovo, and imagine that being applied to Chechnya or Tajikistan.