It used to be that ALT+CMD+SPACE opened up new finder window. And without making any update to my mac, it started opening up finder in search mode. What could have changed? How to turn it back?
As far as I recall ⌘n has always been the Finder shortcut for New Window assuming that Finder is the active app, ⌘⇧n opens the Finder with search focused globally. See the 'Shortcuts' tab of Keyboard.prefPane:
I assume that ⌘⇧n as a new plain Finder window was being provided by some other means; Some configuration in that Shortcuts tab (perhaps under services), or a third party app that does a simple "bind these keys to this action", and for some reason that app failed to start, or crashed if you didn't even reboot your Mac.