You can battle every one of the Battle Frontier Brains as many times as you want. You would have to do be able to do this because when you lose against a trainer after beating a Frontier Brain, you have to start over. The Battle Frontier will always be there to beat, in order to continue to the next round. I've only beaten Lucy once, after losing about four times. I've battle Tucker once, and lost.