Localization is always done with respect to a map.
SLAM(Simultaneous Localization and Mapping). As it is in the name, also does localization with respect to a map. The only difference is that the map is unavailable so it has to create it. It is simultaneously creating a map, and then localization itself against it.
How does the position probability update differ between the two?
Mathematically they end up being the same thing. Just that in SLAM typically the uncertainty of the map is a factor in the position probability. (Should be done in localization to, but is sometimes ignored)
In particular I'm curious on if localization is a fundamentally easier problem give you have map.
Yes. As the map can be created offline you can spend a lot more computing power, and do a lot more refinement to ensure you have a high quality map. SLAM basically has to do everything in real time.
This is why actually most autonomous car companies don't do SLAM, they do mapping and localization separately. They first run there cars through a city to generate high quality maps. Then when it is running autonomously it is just localizing itself against that map.
If you have a strong prior then just remove the parts of the pointcloud that you know will not be in range. You also want to make sure that your ICP algorithm is robust against outliers.