Very often, when some unknown company is calling me, in couple of seconds I see its name and logo on standard Dialer's screen. Where does it take them, if I don't have this contact in my address book, nor do I have it in contacts in any social network, like FB, LinkedIn, etc? Does it search Google right at the moment of the call and shows me the result?
You didn't explicitely mention it, but from the context I assume you're using a device with Android 4.4 (Kitkat). With that, Google "pimped" the dialer. PhoneArena writes on this in an article called Google makes the Dialer awesome again: this is why you want Android 4.4 KitKat:
I think the best new addition though comes in the changes to Caller ID, because that has been supercharged with Google as well. Now, any time you call a number, or receive a call from a number that can be matched to a Google Maps business record, Google will show you that business name, and possibly a picture (though that part of the feature has been a bit dodgy so far), instead of just the phone number. This means far fewer mystery phone numbers in your call history, and if you're like me, it means even more than that.
Also see Android 4.4 KitKat dialer will add Google+ Caller ID and enhanced search options for a second source, and AndroidPolice's Google Does Caller ID: KitKat 4.4 Matches Numbers Against Google Places, And Starting In 2014, Google Personal Accounts for a third.
If it's not that, you most likely have a CallerID app (pre-) installed which does the same: matching numbers of incoming calls against some online database.