His Palkia, if I remember correctly, is Timid and has perfect Speed. Anything with a Speed stat of 100 or less, unboosted, cannot outrun Palkia. That being said, I noticed Mysterial very often opens with Charizard and Palkia, which means he'll use Surf and Protect first turn, no matter which two Pokémon you send out. Lucario also has Protect. If you're playing the Pearl version, my guess is that he Protects with Meganium or Lucario while Dialga uses Earthquake. Either way, this means you should concentrate your attacks on Dialga or Palkia, as they are easily the strongest members of his team.
Of course, if you have trouble with the other trainers, this is what I remember their gimmicks are:
#1 - Uses six Pokémon with a x4 weakness, and all hold Berries that reduce the power of that attack. Bastiodon is holding a Shuca Berry. (There is very little cooperation among Pokémon in this team. They all do their own thing. Even with the Berries, however, since they cover x4 weaknesses, they can still be KOed in one hit by those types.)
#2 - Clefable stands there and uses Follow Me while the other Pokémon use Bulk Up or Calm Mind. When they attack, Clefable uses Cosmic Power or Moonlight. (Clefable is also this team's biggest weakness. Its walling capabilities are great, however, and nothing takes it down in one hit short of a very strong Fighting attack or a boosted Porygon-Z. This trainer nearly always brings out Clefable first; once you knock it down, the team pretty much falls apart.)
#3 - Gastrodon and Lumineon use Storn Drain to divert Water attacks away from the rest of the team, all of whom are weak to Water. (Surf will still hit the partner even with Storm Drain in effect. Also, watch out for Golem--it's a Choice Scarf Exploder with maximum Speed, so unless your Water Pokémon is very fast, be prepared to Protect or switch to Ghost Pokémon when you see it.)