I've found that the best way to smash the CPU quickly is to use the promo legendary Zapdos.
Promo Legendary Zapdos x 1-4 (one you get easily from the Pokemon Dome, the other three you can get by putting Dark Raichu, Raichu, Zapdos and Bill's PC in Bill's Machine; however, you only need one to build this deck)
Lightning Energy x 26
Full Heal Energy x 4 (not to attack, just for four extra full heals and to use for super potion/super energy removal)
26-29 trainers -- Bill's Teleporter, Bill, Energy Removal, Super Energy Removal, Pokeball (if you have more than one Zapdos), Defender, Potion, Super Potion, Gust of Wind, Full Heal x4, Challenge! (if +1 Zapdos), Computer Search (if +1 Zapdos), etc.
This is a simple and quick strategy. You'll reshuffle till you get a Zapdos. Build him up till you get three energy all the while trolling your opponent with trainers, then just use Big Thunder--which does 70 damage randomly to a Pokemon other than the Zapdos who uses it--till you collect your prizes. Note that if you have more than one Promo Zapdos you shouldn't put it in play until your current Zapdos is nearly knocked out, as there's the risk Big Thunder could hit him if he's on the bench.
This can finish off the CPU in 4-5 minutes 90% of the time, and is I think better/faster than the Rain Dance decks I always see posted. If you have more than one Promo Zapdos it's even faster and essentially unbeatable.
Did Nintendo/WoC ever have any say in vetting the promo Zapdos card exclusive to this game? It's incredibly broken. It's also really easy to exploit the fact there's no cutoff for the number of reshuffles you're given when you don't draw a basic Pokemon on the first turn.