iPhone 3G apparently has trouble keeping up with indexing, ever since 3.x
When iOS4 was put onto my 3G, it crippled it. So, the fix.....turn off Sporlight (the search indexer)
Settings-General-Home Button-Spotlight search-switch off the ones you don't use. I've turned them all off, and it's instantly made a massive difference.