Maybe they'll have an organization based on Guerillas. They could ambush the player out of no where and battle you at certain intervals. They could want to take your pokemon. The leader could seek to overthrow the local pokemon government (or I guess League) to rule the region, with an army of grunts marching in at the Pokemon league, too many that it takes the E4 teaming up with the gym leaders and rivals/friends to stop using all their pokemon. The legendary pokemon is needed to prevent the incoming army.