¿Existe alguna manera de buscar aplicaciones instaladas? (Alternativa de Búsqueda Simple)

Puedes revertir a tu comportamiento completamente antiguo. Sin embargo, necesita un poco de hacking y podría ser ilegal (descompilar y recompilar la app de Google)

Antecedentes: Si no tienes acceso root, no puedes instalar la versión antigua sobre la nueva.
Lo que podrías hacer: Instalar una app con las funciones de la antigua app de Búsqueda.
Idea: Si la antigua app tenía un nombre de paquete diferente, podrías instalarla junto a la nueva app.
¿Cómo? ¡Apktool!

Propuesta de solución:
Utiliza apktool para descompilar y cambiar todo el espacio de nombres de com.google.android.googlequicksearchbox a com.google.android.googlequicksearchbox2 de un .apk antiguo y funcional (ver .zip a continuación, presta atención al 2 al final), luego recompila e instala el paquete recién creado.

Resultado: Los proveedores antiguos y nuevos (dañados) pueden ser instalados uno al lado del otro al mismo tiempo porque tienen un espacio de nombres diferente (.*searchbox2 en lugar de .*searchbox). Solo descubre cuál es la antigua y úsala.

Beneficios: Se requiere sin acceso root, permanente (no se puede quitar)
Desventajas: Obtienes 2 veces el mismo widget ofrecido (1 vez del antiguo, 1 vez del nuevo), así que debes descubrir cuál funciona y cuál no

Mi prueba hasta ahora ('apktool' es un alias de 'java -jar /usr/local/bin/apktool.jar' en mi máquina, para tu información):

apktool decompile GoogleQuickSearchBox.apk appdir
#agregar '2' a cada ocurrencia del espacio de nombres
find appdir -type f | while read a; do sed -i 's,uicksearchbox,uicksearchbox2,g' $a; done
#renombrar el directorio para reflejar eso también
mv appdir/smali/com/google/android/googlequicksearchbox smali/com/google/android/googlequicksearchbox2
apktool build /tmp/bla.apk appdir
#Cualquier tipo de firma (jarsigner, signapk.jar,...):
java -jar /tmp/signapk.jar /tmp/certificate.pem /tmp/key.pk8 /tmp/bla.apk /tmp/gsearch2.apk
adb install /tmp/gsearch2.apk

Solución antigua

Lo que sería bueno saber: ¿Esto solo afecta a los clientes de Samsung y Google en EE. UU.?
Según Android Central, Samsung ahora implementa esta actualización como una corrección de estabilidad a nivel mundial.

Muy probablemente este paquete fue el que se "actualizó":
com.google.android.googlequicksearchbox (ubicado en /system/app/GoogleQuickSearchBox.apk)

Definitivamente se necesita acceso root para revertir la situación.

Sin embargo, yo decidiría deshacerme por completo del firmware de Samsung e instalar CyanogenMod, por ejemplo (esto podría ser incluso más fácil que obtener acceso root en el firmware original).

Quizás quieras "reinstalar" la versión no afectada del último firmware o uno de un firmware europeo (si no están despojados). Por ejemplo, este archivo del popular sitio de alojamiento Goo.im probablemente tendrá un .apk (más antiguo) funcional que tiene la funcionalidad que extrañas. Es un paquete de instalación genérico para el popular firmware de posventa de Cyanogenmod que contiene todos los paquetes propietarios relevantes de Google (que tuvieron que ser eliminados de Cyanogenmod por solicitud de Google hace algún tiempo). Puedes abrirlo con cualquier programa descompresor y extraer el paquete /system/app/GoogleQuickSearchBox.apk.

Así es como lo haría (usando la herramienta adb del Google SDK):

adb push GoogleQuickSearchBox.apk /sdcard/
adb shell
su
mount -o remount,rw /system
cp /sdcard/GoogleQuickSearchBox.apk /system/data/
mount -o remount,ro /system
reboot
exit

He utilizado Application Explorer para generar esta lista y ver dónde se encuentra el .apk:

Nombre de la App: Búsqueda de Google
Nombre del Paquete: com.google.android.googlequicksearchbox

[...]

Directorio Fuente:
/system/app/GoogleQuickSearchBox.apk

Puedes obtener la versión de 'Búsqueda de Google' yendo a Configuración->Aplicaciones->Todos->Búsqueda de Google, que muestra la versión actual. La mía (la misma que en el .zip mencionado anteriormente es: 1.4.1.299849)