I’ve had my iPhone 3G now for about 2 years, and it has gotten slower over time. I noticed that it had nothing to do with runnings apps or ‘being too full’. Restarting it or removing unused apps didn’t make it any faster, for instance.
After a quick backup & restore in iTunes (right click your iPhone, choose Backup, wait, then choose Restore from Backup) the iPhone is snappy as new – even when it’s chock-full of apps!
Update: Especially for iOS4 with a 3G, turn off Spotlight if you’re not using it! You can find this setting under Settings/General/Home button. Makes a big difference.
Did it work for you too? Let me know in the comments below!