Backup your database ...

Go into phpMyAdmin and click on the table:
configuration

Now click on the link for Search

Under the configuration_key set to:
Like % ... %
MODULE_SHIPPING_EXPRESS

Delete all of those ...

What happens now?

Sounds like your file is not setup to delete/add all the keys right ...