Sometimes Bulbapedia will say they use high-levelled Pokemon in rematches, but I challenge them over and over and their Pokemon don't level up. Note that I'm mostly interested in generations 3-5.
It's not time based, it's based on how many gym badges you have the next time that you battle them. Usually every other gym badge or so.
Some don't change though. Most do.