The case was that the update manager itself was installed more than year and a half ago and it has gigantic repository - dozens of GB and hundreds of patches and bulletins...:)
I was recommend to update all host to 3.5 Update 5a (which breaks all previous patch inheritance) and reinstall the update manager.
It helped and now scanning last for 30 seconds.