Eliminar accidentalmente el historial de búsquedas en una tablet Android (como la Nexus 7) suele ser irreversible. A diferencia de un ordenador con papelera de reciclaje o herramientas forenses, los sistemas móviles no guardan copias de seguridad accesibles del historial de la app de Google.
Al pulsar "Borrar todas las búsquedas en el dispositivo", Android elimina la base de datos local de la app de Google. No hay papelera, ni carpeta oculta en formato HEX, ni registro recuperable sin root avanzado y conocimientos forenses, algo fuera del alcance del usuario promedio.
En resumen: si borraste el historial local y no estaba sincronizado en la nube, se perdió definitivamente. No hay carpeta secreta ni truco casero para recuperarlo.