> Assuming it is only composed of [LRTB], is there any way in which the
> string can be invalid other than too many folds in a particular dimension?

Yes...  too few folds. The 16x16 (or MxN) paper should be reduced via
folding to a 1x1 stack.  Knowing that the input dimensions should be
powers of 2, you can determine the exact number of folds.  If the
paper is 16 wide, there should be exactly log2(16) == 4 horizontal
folds.