Answering because the previous answer was incorrect.
>Additionally, its Speed is reduced to 25% of its previous value (except for Pokémon with the Quick Feet Ability, where this condition raises the Speed by 50%).
It's only 25%. Deoxys-S has a max Speed of 504. Let us see what it is after:
504 / 4 = 126.
If Ferrothorn was running 204 Spd EVs with a neutral nature, nature, or 160 Spd EVs with a +Spd nature, Ferrothorn would outspeed a paralyzed Max Speed Deoxys-S.
If Deoxys-S used ExtremeSpeed, it would go first, as it is a priority move.