Here is a rewritten location_search.module. It uses the search apis and is able to do fulltext searching. It's also cleaner, and will be ported to Drupal 6.

It searches by location, not node. (Restriction to specific types of objects is possible but not implemented yet.)

Hopefully I didn't accidentally leave out / forget any features people were using.

It will need to generate a search index before it will work properly, so do the same thing you would do if you were reindexing the site (i.e. run cron in a loop and watch the percentage indexed number)

Minor api change (optional):
* Add an 'instance_links' op to hook_locationapi so modules can stick in the correct urls for the instances they handle.

* Fix $op 'delete' on hook_locationapi().
* API CHANGE: Use location_save_locations() with an empty array instead of deleting rows from {location_instance}. This lets us have "real" deletion instead of relying on garbage collection.

Before:
<code>
db_query("DELETE FROM {location_instance} WHERE genid = '%s'", 'mykey:'. $obj->id);
</code>

After:
<code>
$locations = array();
location_save_locations($locations, array('genid' => 'mykey:'. $obj->id));
</code>

* Remove garbage collection routine and UI from settings page. References are checked automatically now.

#317048, reported by carlogen: Repair some completely broken views 1 code, namely the province and country exposed filters.

Repair broken update that failed to change the weight of location_fax and location_phone. (Preemptive backport of uncommitted Drupal 6 changes.)

#315705, reported by mburak: Be nice to the Drupal 5 themers and check for overridden templates, instead of making them do a full template.php override.

Split token support into its own include file.

Fix how defaults are used when expanding location elements. This eliminates warnings after enabling location_phone / location_fax, and lets 'collection default' work as intended.

Fix #314835, reported by marcoBauli: Make collapsibility work again. I had accidentally broken this while fixing notices.  Additionally, collapsible now works on single-location forms.

Move location_province_select_options to location_views and modify it a bit. It still has caching issues.

Backport commit 131997: Rip out the notion of "supported countries." With the dynamic country loading, this isn't really needed.
This breaks some of the "province listing" stuff, but it needed work anyway.

Backport rev. 1.178 (http://drupal.org/cvs?commit=139455): Only include textfield for 'Additional' when 'Street' is 'Allowed' or 'Required'.

Backport commit http://drupal.org/cvs?commit=139463 by ankur. Enforce required fields for just the first location when there are multiple location form inputs. (Some comments added)

Convert to update_sql to hopefully get more feedback on the problem where some people aren't having location_instance installed properly. (#301542, #298306)