For Barry, you have to beat Cynthia 20 or 25 times (don't recall which). His levels go up only once.
As for the others, check out this link:
http://upokecenter.com/games/dp/guides/trainers.html
The rematches begin at row 627 and end at row 777. You'll have to use another document (there are a few FAQs over at GameFAQs that work) to actually find out where the trainers are, though. The deal is, once you passed a certain point in the game, when you use the Vs. Seeker on one of the upgradable trainers (keep in mind several trainers don't upgrade their rosters, ever), the levels of their Pokémon go up, and they might evolve, too. Now, if you haven't touched a trainer since you first fought him/her and you caught Heatran, he/she won't have her final roster just yet. Let's take the example of Aroma Lady Elisabeth. The first time you use the Vs. Seeker on her, she'll have a level 19 Budew. If you use it again immediately after (or any time afterwards for that matter) she'll have a level 31 Roselia, and then a level 51 Roselia. However, I believe catching Heatran is the final trigger for upgrading certain trainers, so you should do that first.
Finally, two notes: don't bother with the level 5 Rattata rows, they're filler. Also, the trainer called Artist Kevin in the rematches was actually called Artist William in the first battle, so if you look up Artist Kevin you won't find him anywhere (there's a Hiker Kevin though). If memory serves me correctly, he's on route 208 (between Mt. Coronet and Hearthome).