Could you see whether this is a category in the Clear Private Data screen? This article describes how to use that feature: [[How do I clear private data on Firefox for Android?]] If the search is running through a widget on the home screen, that probably is stored by Android outside of Firefox. If you can find that search widget in Manage Applications, you could try clearing its cache or, more drastically, deleting its data. This probably varies depending on your device and Android version.