As Rainbow definitely knows she isn't possessed, she can explore one of the corridors alone. The problem is figuring out how to divide the rest of them.
Let's imagine you decide to send at least one group of four down one of the paths. That's a no-go, because what happens if they come back and they're in disagreement over where the exit is? If they're evenly split, then you'd have to guess who's lying and who's telling the truth.
But sending Rainbow, a pair and two groups of three down the four paths WOULD work.
When you come back to the room to report, you just listen to each group (assuming Rainbow doesn't find the exit herself). The groups will either give the same report over whether they found the exit, or there will be an argument breaking out. Now, one of three things can happen:
Good thing Rainbow heard about this puzzle from one of the Daring Do books, eh?
Wait, but Rainbow isn't fast enough ?..