I think providing more items in the relatively sparse categories would be good - bracers, boots, girdles, and cloaks come to mind. Items with Paralysis resistance would fit fairly nicely into all four of these categories. Some ideas for specifics for each of them...
Bracers of action [+1,+0], Mithril (unIDed: "mithril bracers"), 18s, -Para -Stun <- Protects wearer from action-preventing statuses
Boots of the messenger [+1,+1], same material as SLB (unIDed: "fleet boots"), 30s, {Dx+1} -Para <- A weak form of Boots of the divine messenger, can't be distinguished from SLB when unIDed.
Girdle of reaction [+4,+0], same material as girdle of weight (unIDed: "curious girdle"), 40s, (+5 speed) -Para <- Only girdle that boosts DV, cannot be distinguished from girdle of weight when unIDed (thus addressing a problem with the girdle of weight at the same time)
Cloak of freedom [+1,+0], same material as cloak of invisibility (unIDed: "patterned cloak"), 30s, {Wi+1} -Para <- cannot be distinguished from cloak of invisibility when unIDed.
All four would be rare, with girdle of reaction being most common of the four, but all less common than AoFA. I tried to give each one its own feel, and where possible/appropriate, duplicate unIDed properties so that it's harder to identify items just by looking at weight or things like that.
I'd also suggest having a new suffix available for weapons, of the form "of action", providing Paralysis resistance.