(EDIT) New solution:
You can revert to your complete old behaviour. It needs some hacking though and might be illegal (decompile&recompile Google app)
If you don't have root, you cannot install the old version over the new one.
What you could do: Install an app with the functions of the old Search app.
Idea: If the old app had a different package name you could install it next to the new app.
Use apktool to decompile and change the whole namespace from com.google.android.googlequicksearchbox to com.google.android.googlequicksearchbox2 of a working old .apk (see .zip below, mind the 2 in the end), then recompile and install the newly crafted package. Result: Old and new (broken) provider can be installed next to each other at the same time because they have a different namespace (.*searchbox2 instead of .*searchbox). Just find out which one is the old one and use that.
Benefits: No root required, permanent (cannot be taken away)
Drawbacks: You get 2x the same widget offering (1x from the old, 1x from the new), so you have to find out which works and which not
My test so far ('apktool' is an alias to 'java -jar /usr/local/bin/apktool.jar' on my machine , FYI):
apktool decompile GoogleQuickSearchBox.apk appdir
#append every occurrence of the namespace with '2'
find appdir -type f | while read a; do sed -i 's,uicksearchbox,uicksearchbox2,g' $a; done
#rename the directory to reflect that too
mv appdir/smali/com/google/android/googlequicksearchbox smali/com/google/android/googlequicksearchbox2
apktool build /tmp/bla.apk appdir
#Any sort of signing (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
(EDIT: Old solution)
What would be nice to know: Does this only affect Samsunng and Google's US customers?
According to androidcentral, Samsung now deploys this update as a stability fix globally.
It's most probably this package, that got "updated":
(located at /system/app/GoogleQuickSearchBox.apk)
Having root is definitely required to revert the situation.
I'd however decide to get rid of Samsungs firmware altogether and install CyanogenMod for example (This might even be easier than getting root in the first place on the orginal firmware).
You might want to "reinstall" the unaffected version from the last firmware or one of a Euro firmware (if they're not stripped). For example, this archive from the popular Goo.im hosting site will most probably have a working (older) .apk that has the functionality you miss. It's a generic installation package for the popular Cyanogenmod aftermarket firmware that holds all relevant proprietary packages from Google (they had to be stripped off Cyanogenmod by Google's request some time ago). You can open it with any unzip program and extract the /system/app/GoogleQuickSearchBox.apk package.
That's how I would do it (using the adb tool from the Google SDK:
adb push GoogleQuickSearchBox.apk /sdcard/
mount -o remount,rw /system
cp /sdcard/GoogleQuickSearchBox.apk /system/data/
mount -o remount,ro /system
I used Application Explorer to generate this listing and see where the .apk is located:
App Name: Google-Search
Package Name: com.google.android.googlequicksearchbox
You can get the version of 'Google-Search' by going to Settings->Apps->All->Google Search, which lists the current version. Mine (the same as in the above mentioned .zip is: 126.96.36.1999849)