This suggests to me that either :
#1) the way traffic counting and Search->Places listing is written makes it cause a lot of load.
OR
#2) each place listed doesn't cause that much load, but there is still a lot of load because so many places are listed.
Obviously, if it is #1 that is the problem, it'd require coders to fix that.
If the problem is #2 on the other hand, have you considered charging more for a Search->Places listing to compensate?
Customers hate having to pay higher prices for things then they are used to. Believe me, I know, I'm an island owner

On the other hand, setting the minimum fee for a classified ad, and for listing a parcel in Search->Places to around L$100 each per week, would :
1) raise money for LL.
2) mean that unpopular places were less likely to advertise in those media, reducing db load.
3) reduce the occurance of people spamming the search results with many listings for the same product, all priced at L$50 for a classified ad or around L$30 for a places listing.
Frankly I don't know this is a good idea, because I don't know if it would solve the problems with db load, and I don't know how the community would react either.
It just seems to me that charging small but not insignificant fees for the things that cause most db load (like having an inventory of 5-10+ thousand items) might help encourage people to be more efficient and thus reduce the db load. Recycling is good.
Obviously if it's a bug in SL's code that is causing the load issues, then fix that... but if it's not, and it's just due to sheer number of entries in search->places and the classifieds, then this might be an option too.
Having to pay more for search->places listings is imho better than not having them at all. Obviously, having them back without paying more would be the best solution, but some of us run businesses in SL that depend on Search->Places working, and for us, L$30 or so a week is nothing but the search not working is a big deal.
You don't have to say that you're working hard on restoring it. I understand that you are. I imagine you must get a LOT of complaints it is not working. I'm not trying to nag you about it, I'm simply saying that it's better to have it working but be more expensive, take longer, or whatever, than to have it not working.