The problem with NATO not expanding after the Cold War is that the consequences of a power vacuum in central/eastern Europe is vastly more dangerous than the Pre-2008 world OTL. Poland was threatening to get nukes, Hungary and Romania were still arguing over Transylvania and the Balts were terrified of being subsumed into Russia again and wondering what to do with their Russian minorities.
If NATO is ruled out, all these places will know they have no insurance against a renewed Russia that had occupied them for either half a century in the case of Czechoslovakia/Hungary/Romania/Bulgaria or centuries period as with Poland and the Balts. In such a case, it's every man for himself - the Poles would eat grass to get nukes to stop Russia, the Balts will make OTL's language measures look like a hippie commune, and the same corrosive governance that Slovakia had which stopped its initial NATO bid will expand to the entirety of the Balkans. All this will, ironically, make Russia less safe since they've massively increased the geopolitical tripwires across the continent.
Your only chance might be to make Partnership for Peace take over, but that was all dependent on Russia upholding her end of the bargain to create western institutions and for Eastern Europe to feel they didn't need insurances. Russia by 1996 had been involved in multiple military operations of dubious nature (Transnistira, Chechnya), was universally considered to have rigged the vote to stop an even more authoritarian candidate taking over, and was already swept in a wave of Brezhnev nostalgia - Eastern Europe was not going to sign up for this when a tried and tested solution in NATO already existed. Incidentally NATO expansion was only a blip in West-Russia relations - Yugoslavia was a bigger flashpoint since it was the West interfering in Orthodox Slavic territory that Russia thought so important that WW1 began over it. Even then Russia's hatred of NATO wasn't a big deal until after the Orange Revolution and the thought of an Eastern Slavic country joining NATO (since now Ukraine had an openly Pro-NATO government albeit an Anti-NATO populace) - Putin barely reacted to the Baltic ascension because the Balts were non-Slavic and non-Orthodox, even less than Poles, so Russians basically accepted that they weren't part of their world in a way they wouldn't say in regards to Belarus or Ukraine. Hell I've even seen some analysts say he was more pissed that Romania and Bulgaria joined NATO both due to their being on the Black Sea but also the sense that these were peoples united to Russians in the Orthodox faith (and broader Slavic identity with regards to Bulgaria).