I myself have been using Android phones (including an S3 in the past) for a long time, and I've never experienced such a slowdown.
1. What could be the cause of this? Unavoidable periodic bloat/slowdown? Maybe some sort of malware/bloat (I won't rule my dad out from falling for sketchy looking apps)
2. Any tips or suggestions on how to fix this? Or is a factory reset the only way?
3. Is there any pure Android ROM (without TouchWiz) which is as stable as the stock ROM? Keep in mind it would be my dad using it and I can't really expect him to reflash by himself in case he encounters a major problem.