In reality that search history was never persisted outside the Firefox app.
The data is certainly persisting somewhere outside of Firefox proper, as the search app is siphoning data that can only be cleared from within.
That does not follow. They are the same application.
For example, attempt to reproduce this after pressing the Clear Data and Clear Cache buttons on Firefox's Android app info screen.
In reality that search history was never persisted outside the Firefox app.