Bitcointalk search could be annoying when you are looking for information, but not for slowness when you search for anything. There are two possibilities for your experience. It might be the fault of your internet/browsers or you unfortunately made the search when the site is having its downtime moments.
This is absolutely true when it comes to searching some information. I do experienced same problem when searching but I use to assume that perhaps it's due to too much similarity of words used in the forum. Try searching for a user Forum name and you'll see numerous of suggestions including the non relevant ones. Annoying enough, sometimes you still won't find the information you are looking for. Other aspects are actively working fast as long as the internet connection is not interrupted but the searching function needs some little improvement in order to be providing relevant information.
Maybe something is definitely wrong with your internet connectivity or the device you're using, have you also considered the availability of space on your device memory, search engine is not what should last than seconds to have your results with you, or maybe you probably make it more difficult to search through by what you typed in to be searched for, there's nothing wrong with the forum search here than from your end.
Does this has anything to do with one's phone storage available space? I doubt that. The search is not downloading any file but just to provide us with readable informations. So I think it has less to do with storage so far your internet connection is strong. The searching function is actually working fine but my own concern is the information it use to bring out.