For third (case III), We can treat M like an LBA with a input tape size n. The key to seeing that this is decidable is to recognize that M in III is being restricted to basically a LBA.
One possible way of deciding would be,
On input <M, n>:
From n, get the possible number of distinct configurations c (finite in this case) of an LBA with i/p of length n. Simulate M for c steps, keeping trck of no. of distinct i/p symbols that M scans or till the no. of distinct i/p symbols scanned equals n, which ever case comes first. In the latter case, accept. After completion of c steps, if the no. of distinct i/p symbols scanned = n, then accept. Else, reject.
Hope this helps.