If you have the setting turned ON, the game will search for anyone, including the last opponent you've fought against.
If you have the setting turned OFF, let me explain it with an example:
> Player 1 has previous opponent ok ON, player 2 also has previous opponent ok ON.
> Player 1 finds Player 2 (''A new challenger appears!'').
> Player 1 cancels the fight.
> Player 1 sets previous opponent ok OFF, player 2 still has it ON.
At this point in time Player 1 is unable to find Player 2, and vice versa.
> Player 1 searches again with setting OFF and finds Player 3 (''A new challenger appears!'').
> Player 1 cancels the fight.
At this point in time Player 1 is able to find Player 2 again, because Player 3 was the previous opponent of Player 1! So after cancelling the fight against Player 3 it is impossible to find Player 3, yet Player 2 can be found again because he isn't the previous opponent anymore.
> Player 1 searches again with setting OFF, and finds player 2 who still has the setting ON.
In conclusion, the game will only exclude the last person you've encountered. It doesn't matter if you have fought against that opponent or not, the ''A new challenger appears!'' screen is the one that counts.