I think, at least when it comes to PCs, SSDs have really helped to reduce the effect of cruft and slow-down over time. The effect of filling up a HDD usually results in the computer starting to slow down, thanks to data becoming scattered over the HDD, and the platters constantly needing to move from sector to sector, and from the outside to the inside and back again to retrieve data. The more data you have on there, the more travelling the platters and the heads have to do to retrieve it (modern operating systems do a pretty good job of optimising where this data is placed though, so it's generally pretty efficient). SSDs remove that element of retrieving data, data can be pulled from anywhere on an SSD without any worries.
I'm not sure why older Android devices slow down. My old 3GS definitely got slower as time went on, it was bogged down with a lot of apps, jailbreak tweaks and music though- the storage on it was almost always full. My iPhone 5, which I started as a new phone to avoid the cruft of my 3GS, is far, far faster- we'll see if it gets bogged down later in its life. Also, there's been a lot of issues with the Nexus 7 when its storage gets full, a lot of people have complained about the device becoming ridiculously slow when under 3GB of storage are free. I've kept mine around the 5GB mark, to avoid more slowdown on it.
