1. By having MIN/MAG filtering to GL_LINEAR, shouldn't I also have visibility = 0.5 for some samples? All I see is either 0.0 or 1.0.
The result of the texture sampler (you have a shadow sampler which do a depth comparision) is either in shadow or not in shadow (use PCF or other fitlerings to get soft shadows). The linear filtering is used to get the right depth comparision value, but the final result is only the binary result of the comparision of the filtered depth value and your reference value.
4. I am using shadow samplers, which gives me 0.0 or 1.0 values. How can I accomplish soft shadows with this for directional and point lights with such binary values to work with?
To create soft shadows , you can't use standard texture filtering methods (eg linear filtering), they will not really work. An often used approach is, to sample multiple shadow samples and calculate the shadow values yourself (eg PCF), I use ie 12-24 samples per rendered pixel to soften my shadows in my engine. Look out for hardware supported filtering too (again PCF).
5. Why would you not use shadow samplers over normal samplers in shadow mapping?
Because the hardware might be optimize to do the comparision of the shadow values, and the hardware could support already some degree of PCF to soften your shadows. In comes all down to better out-of-the-box hardware support.