So I give it a second try and found some interesting thing.
When I login to my account, I immediately disabled to sync settings. Only allowed to sync Passkeeper, QuickAccess and Passkeeper from cloud. So, it synched almost immediately. (Double checked that settings are not synced). Google voice search is working fine.
Then I disabled cloud sync.
But after some time later (1-3 mins) something! also synched from the icloud (I understand this because my theme changes Night - even I never used that theme before) (3rd video). When this happens Google voice search stop working. So, when I click the microphone icon on Google.com, the large mic button flashes but it doesn’t detect or respond to my voice when I speak.
I don't know what triggered this but something breaks the google voice search when it syncs from cloud even cloud sync for "settings" completely disabled (video #2). Also happens cloud sync disabled alltogether (video #3)