I have a slightly weird and a bit too complicated approach to this issue, but it works for me at least:
I’m an avid breeder and have been maintaining a huge collection of 'mons with special egg moves, good IVs (and later Apriballs and hidden abilities) since the breeding mechanic was introduced. Whenever I feel the urge to restart a run on any game, including the “older” ones, I create five eggs for a starter team and let them hatch in the new playthrough. That way I make sure that every team member is useful to me right from the start and I have no issues circling through them depending on which one is the most useful for the climate/zone I’m currently in or which one needs a little more XP at the moment.
Whenever I rely only on the 'mons that can be caught in early routes, I end up overlevelling my starter as they tend to be the most (or only…) useful team member and trying to battle with the others feels like a chore. It’s just not fun to try and fight with a Poochyena that only knows Tackle, Howl, Sand Attack and Growl until it finally gained eight or so more levels to learn its first actually useful attack, and then having to swap it out shortly after that because you need to drag an HM slave with you. =/
The downside is that you either need someone else to help you trade, or use one of the still availiable online storage options to trade with yourself in order to move the eggs or newly hatched 'mons into another game, and Nintendo’s service in that sector isn’t exactly convenient.