My understanding is that "stealth" aircraft are optimized for low observability at X-band (~10 GHz) since that's the band used by most airborne fighter aircraft's targeting radar. They may also optimize for S-band (~3 GHz) from low elevations, since that's the band that's most commonly used for ground-based surveillance radars (that are part of a weapon system - longer range ground radars often use L-band instead).
Given this, it wasn't terribly surprising that the S-125 Pechora could detect an F-117. It also reportedly did so at close range. I found it a bit more impressive that one of these systems shot down a Predator, which would likely have an even smaller RCS, and likely be optimized for low observability to ground radar.
Radar bands are not merely bragging points (as in, "check out my pimped-out fighter with a Ka-band radar"), they're designed to a purpose. For example, radars that look for much lower RCS targets (ICBM RVs) are typically UHF or lower (GBR and TPY-2 are notable exceptions), since they tend to not be as limited by propagation losses. They are also ground-based, and are hence not size-limited.