I'm pretty sure there's a leader from each region that always manages to send me packing, save Sinnoh, coincidentally enough. In Kanto, there's Koga and his team of trollish poison types, featuring the bulky, toxicstalling, Weezing; and the minimize-spamming Muk, who also boasts considerable bulk. In Johto, we have Clair and her behemoth of a Kingdra, which will spam smokescreen if none of it's 100+ base power attacks can harm you. Whitney and her Miltank are still a bit of a challenge for me, but I've battled them so much, that it's become second nature for me to beat them. Hoenn's Watson and his Magnets, Exploding Voltorbs and powerful Manectric (Emerald) is pretty much hell if, you didn't pick Blaziken as your starter. They've even found ways to kill my Marshtomp. Even if you find something that resists his arsenal of electric types, they will still proceed to paralyze you and then whittle you down with a Sonicboom, which is surprisingly effective, as most of your Pokemon have no more than 50 HP, at this point. Steel typing, this early in the game, is pretty crazy stuff, too. In Unova, there's 2 gym leaders that have and will continue to, give me a run for my money, the first being Aloe. Her bulky and powerful Herdier is hard enough to kill, coupled with that is a tenacious Watchog, that will proceed to hit the Pokemon that just took out Herdier with a 140 base damage attack. Not to mention hypnosis, because it wasn't already tough enough to beat. The final gym leader that has given me trouble, would have to be Elesa. Her Zebstrika is quite easy to kill, but those Emonga, sheesh. They spam double team until they're virtually unhittable and then use Volt Switch to send in her Zebstrika, which is a bit harder to beat than when your accuracy wasn't lowered by 6 stages.