I have a theory about what's going on here.
When I first got my iPhone 3G, it was very snappy. Then I loaded it almost full with music and video, and it slowed to a crawl. It's never been the same since. Removing the media didn't help much, and even a full system restore didn't help any further.
As you know the iPhone 3G has only 128MB of DRAM. When that's not enough, like any modern OS, it swaps pages to "disk", that disk being the flash drive (16GB in my case).
My theory is that with so little free space, the wear leveling was confined to a small space, the logical to physical sector mapping got fragmented, and as a result, write performance got very poor. Removing the media helped because it allowed the wear-leveling algorithm to use more of the disk when writing to swap, but nevertheless it continued to get more and more fragmented over time. Restoring to factory settings doesn't help because the logical/physical mapping is managed in the drive, and that isn't reset when you restore the device.
With iOS4, the pressure to swap pages to/from disk is even greater, causing even greater and accumulating fragmented disk blocks. The result is very poor write performance that gets progressively poorer.
The fact is, the iPhone 3G just doesn't have enough DRAM for the new OS. And Apple has failed to do something really fundamental to help with this, which is to do background defragmentation of the solid-state drive.
The reason that newer devices with 256MB+ of DRAM don't have this problem is because swap pressure is dramatically reduced. Regular app performance isn't affected so much because reads are still fast, although even they should notice gradual slow-down of apps that do a lot of writing to the drive (which fortunately doesn't happen all that much).