Just thought I'd crunch some numbers here, since we're adhering to game mechanics. Forgive me if it sounds excessively cold, but numbers are just that.
I'll take into account each poke's maximum possible speed, for fairness' sake (since it seems we might need that)
Kingdra: max IV, +speed nature, 252 speed EVs=358 total speed
Paralysis: 75% speed reduction
+2 levels in speed (+100%)
(358x2)/4=179 speed.
Dragonite: max IV, +speed nature, 252 speed EVs= 347 speed. Even without a +speed nature or EV investment, D has 259, which still outshines your ailing seahorse.
Now, which is the bigger number?
Playing the way you are, with speed affecting evasion, one would assume that speed also determined accuracy. 259>179, just remember that.
Now I'm not in a position to force anything, but I don't think you should have avoided at least half of what you have.