Paralysis scaling is weird, yeah. The thing is - and this might sound counterintuitive - poison effectiveness doesn't actually scale with enemy level the way damage does. Your paralysis poison lands the same on a level 5 bandit as a level 35 draugr, but by that point enemies have way more health and resistances, so it feels useless even though it's technically working.
On Legendary the problem gets worse because everything just has bloated HP pools. A paralyzed enemy is still a paralyzed enemy, but if you're not one-shotting them during that window, you're basically wasting the poison.
What actually helps more than stacking different poisons is getting the alchemy perks that boost duration and potency - there's one that makes poisons more effective per rank, and another that lets you apply multiple poisons to a single hit if you're on PC. The PC version also has mods like Alchemy Adjustments that rebalance how poison scales, which makes it feel less cliff-like. On console you're kind of stuck with vanilla scaling though, which sucks.
If you want paralysis to stay relevant, honestly you're better off leaning into a hybrid build - get some decent one-handed damage or archery going so you're actually killing them during the stun, not just... watching them stand there paralyzed while you reload. Paralysis is a setup tool, not a finisher by itself past early game.