Lower the amount of times you can fight the same person within one hour to 2 times per hour instead of being 5-6 times in one hour. This will help ease the frustration of many players. Especially those who not only get the same player but someone they have little to no hope of beating without extreme luck.
So what about the increased wait time during beginning and ending of day? Maybe it tries for 5 seconds and if it can't find a different opponent fight them. (This won't be a problem this weekend though)