I'm guessing it's because 'the' is only used to indicate specific items/situations whereas this sentence refers to a situation in general. So, for example, 'They have the yellow bananas and they have the green bananas' (referring to specific people and specific bananas) vs 'Bananas are never pink' (referring to bananas in general). It is possible to say, 'They never have the red balloons' in a situation where we know that there is a specific kind of red balloon somewhere that they could have had. However, that doesn't apply in this case because 'they' can only have the soles that they have. Yes, those soles can be clean or dirty, but they remain the same soles. So if they are never clean, they will always be dirty and vice versa. We are talking about a general situation not a specific one.

As it happens, I find it hard to think of a situation in which an English speaker would say, 'They never have clean soles' anyway. Much more likely: 'They never have clean feet' or 'The soles of their feet/shoes are never clean' or even 'They never wipe their feet' - meaning that they don't get the dirt off the soles of their shoes before they come into the house. As it stands, the sentence just sounds odd to me.

Yes

By now you probably know the answer is yes.

Yes, both cases can apply.