Search speed increase
If you doing on a regular basis UPDATE and/or DELETE statements on a table the SELECT speed will decrease over time because the data and indexes (if present) will be fragmented thus the search process will take more depending on the degree of fragmentation so i purpose :


to run OPTIMIZE on the afflicted table on a regular basis (once a day should be enough) because this will defragment the data and rebuild the indexes (if present)
add indexes (if you do not already have) on the columns most commonly used in SELECT statement