Complexity of membership testing for finite-regular languages
Finite-regular languages need not even be decidable. Indeed, if $L$ is any language such that $|L \cap \Sigma^n| \leq C$ for some $C$ independent of $n$, then $L$ is finite-regular (you can show this by considering the case $C=1$). In particular, the language $\{ 1^n : \text{ the $n$th Turing machine halts on the empty input} \}$ is finite-regular but not decidable.