Default Phone unbearably slow, Play Store not installing apps (not enough storage, not true)

My father is complaining a lot lately that the phone is even slower than usual and that apps are not installing. I checked it out myself and while I find stock ICS on these devices literally unusable even after a fresh install, this time it's worse than anything I've ever seen, apps take several seconds to open and the phone chugs along at a snail's pace. On top of that, I can't install **** even though I have over 100Mb free internal memory, yet the Play Store keeps complaining about not enough storage available.

I have no idea how the phone became this slow, like I said before, ICS is a clunky sluggish mess on 2011 xperias, but now it's even worse, and my father other than the stock apps only installed Whatsapp.

So yeah, how do I make this piece of crap usable and how do you fix the storage issue? Google gives me a billion different solutions and not a single one works.

Phone is rooted on stock ICS latest, model is ARC S.

Formatting the phone is not a solution, so I can't install another rom (unless you can keep the data partition).