I used a Moto Milestone, one of the early popular Android phone, with Android 2.2 a.k.a. Froyo (the ROM was built for some European carrier because Milestone, the GSM counterpart of Moto Droid, was not sold by any carrier in the US). The system was very responsive when I wiped all the data and first flashed it on. Then noticeable slowdown appeared as time passed. After trying a few things, I discovered one simple (and easy) cause:
much of the slowdown is due to the growth of user generated data and that some of them are regularly loaded into memory for access (via content providers).
Thus by regularly (backing up if you want to keep the data and) clearing call log, messages, etc, I restore the speed on my phone with ease (without worrying about what is in a new ROM). With the exponential growth in phones' RAM, this will become less a problem and if the programmer practices more care and loads only a small portion of all data at a time: for example, the user does not usually need to see the call history from last week everytime he or she goes into call log.