Do all non self starting counters have lock out problem?
It all depends on your definition of 'lock-out problem'. 

If you define it as 'not self starting', then yes, by a tautology, you are correct.

Sequential counters, as typified by the LFSR, may have sets of states that are disjoint. The classic maximal length sequence in an LFSR has two sets, the 0 state, and the 'counting' 2^n-1 states. If it powers on in the 0 state, it will never transition to the other set. Usually a LFSR contains a few extra gates to ensure the 0 sequence doesn't persist, so this potentially 'unexitable' state can be left with special logic that avoids it being a 'problem'

If the LFSR has an other than maximal sequence length polynomial, then it will often have multiple disjoint sets of states. If you define one set as the 'counting' set, then you could define each of the other sets as a lock-out sequence, so it would have multiple lock-out sequences. Again in a practical counter, you' probably add some extra check logic to kick it from any of the unwanted sequences and onto the main sequence.