ok, I figured it out. Contacts were synched with a Samsung cloud and so when I disabled the bloatware, I also disabled the Samsung cloud crap. Because of that the phone lost connection with the cloud and removed synched contacts. Only few were available, those that were not backed up as of yet.
Problem solved by enabling the Samsung cloud apps again and synching contacts with the phone.
Then synch everything with google. I can lose my phone and buy the same one (with 4.4.4) and it restores nearly everything.
