can not install-update anything with over 500mb free?

Android needs some free "working space" for caching temporary files. In order to maintain the stability of the system, the operating system will require some minimum amount of free space, and will refuse to install apps if doing so would take the free space below that minimum. Only internal storage is relevant here: it does not matter how much space is available on a removable SD card, since that is not used in the same way.

What the minimum free storage required is varies between devices: it's a parameter set by the manufacturer when they build the OS. On the earliest devices, which had very little storage, it used to be 10%. As storage grew this was replaced by a fixed threshold: in 2011 200 MB would have been normal, by 2014 500 MB was common, and I've seen devices where it is higher (certainly 700-750 MB, and I'd not be surprised if there are devices where it is higher yet).

In short, I'm afraid that what you are seeing is indeed normal. How much free internal space do you have? If you tell us what phone it's possible someone will know what's needed for that model, but no promises (I don't know what the limit is for my phone, because without root and a very deep dive the only way to find out is to hit the limit, and I'm a long way from that at the moment).

They got installed in the first place because you had more free storage then.

I'm afraid this is indeed normal (and it takes more than adding the word "logically" to an assertion to justify the statement - sorry, I've spent most of the last fortnight marking exams, so am a bit sensitive to such things at the moment ). I'm not going to justify the thresholds the manufacturers have chosen: I have used devices where the corresponding threshold was 15MB (where the device only had 147MB of /data partition in total!), and suspect that for most users you could safely set it lower than they do - though some apps are capable of caching a lot of data very quickly, so I suspect they tend to play safe. In any event, there's no point arguing about that, because you cannot change it unless you are going to root your phone and find a ROM that's been built with a lower threshold.

The pre-installed carrier crud might be using less space than you think. Pre-installed apps live in the system partition, which is separate, so even if you could remove them that wouldn't give you any more space in the data partition (which is what counts). However, clearing those apps' data and uninstalling updates to them will free space (app data and updates to system apps do live in the data partition). If you can disable them (sometimes Samsung or the carrier prevent you doing this) that will have exactly the same effect as uninstalling them - the pre-installed version of the app will remain in the system partition, but with no updates, no data stored by it, and it being unable to run or install more updates then it can no longer use any of your space (/data).

Of course if there was less of that crap in the first place the /system partition could be made a bit smaller, so in that sense it does waste space. But Samsung always add a lot of bloat, and their own system software is very heavy, so really if you want something more streamlined they are not the manufacturer to choose. It is one of the reasons I don't buy carrier-branded phones, but not everyone has that choice.

If you are running GT i9506 what does your Storage show as used Internal storage?
Mine shows 11.31GB used of 14.68GB. (16GB's quoted by Samsung) Tapping on Internal storage then shows
Apps using 1.56GB
System using 2.97GB
Other using 5.92GB.
I have rooted the phone and it's running Android 7.1 Nougat.
Can you use Kies or Odin to backup then do a Factory Reset?

Click on apps then sort by size.

As suggested by chanchan05, If you are on Android 5 Lollipop >Settings > Application Manager > Running > should show what is taking up space.
Have you put the phone into Android Recovery? Wipe cache partition?