In 7 Trials To Glory, we have the imaginatively named R. Hunter, one of the game's Shadow duelists. The game's main gimmick is the Shadow World, which allows both players to use absurdly broken Shadow decks. R. Hunter uses a Shadow version of an Exodia deck, which allows him to summon Exodia within about 5 turns. And that's if you're lucky; if not, say hello to a 2-turn instant loss. It really says something when Marik, who has three copies of each of the Envoys in his Shadow deck (which were Game Breakers in the real life game even after being limited to one), is much, much easier to beat than R. Hunter.
The Four Clone fight in Stardust Accelerator is unanimously considered the most difficult fight in the game by a huge margin. As the name implies, it is a Boss Rush, so you cannot simply restructure your Deck to beat one or the others will crush you. The first one is hard but not ridiculous, the second is a pushover, but the third will absolutely wipe the floor with you unless they get ridiculously unlucky. And the fourth is even worse than the third, running a TeleDAD deck (which, for those not familiar with competitive play, was widely considered the most dangerous deck anyone could run at the time Stardust Accelerator was released). And to make matters worse, your Life Points carry over to your next opponent for no good reason. Did you just barely beat your third opponent with a few hundred Life Points left? Yeah...good luck.
Though not nearly as bad as the Four Clones, there's also Lenny. You face him very early in the game, where it's unlikely you'll have any powerful monsters with over ~2400 ATK, or many monster removal cards. Lenny plays an incredibly nasty Insect deck filled with 2600-2800 ATK monsters that he can summon for virtually no cost, and loves to spam Dimensional Prison every time you try to attack him.
Forbidden Memories gives us Priest Seto, in your third encounter with him. Easily the most challenging opponent in the game, primarily for a single card: Blue-Eyes Ultimate Dragon. Which in this game is treated as Normal Monster. Monster removal cards are incredibly hard to come by in this game, but in this duel, they are an utter necessity, as there is no card in the game that can overpower Blue-Eyes Ultimate Dragon even with a Guardian Star boost. And just to add some far too much Fake Difficulty into the mix: you fight Seto at the end of a long Boss Rush campaign, which lacks any chance to save. Which means you WILL have to fight these guys over. And over. And over again. Oh, and by the way, Seto isn't the last battle in said Boss Rush. Who is? Why, the final boss, of course. Thankfully, even the final boss isn't as bad as Seto, but if you get bad draws...well, let's just say tears will be shed.
Marik Ishtar, in almost every game he appears in. In Sacred Cards he is spared from this only by virtue of being the final boss, as he is far and away the most difficult opponent in the game with multiple cards that reverse the entire flow of the game in a heartbeat. In 7 Trials to Glory... well, see the R. Hunter entry above, and note that he also has three copies each of Mirror Force and Torrential Tribute. He's at his worst, however, in Reshef of Destruction, where he will throw out monster-destruction cards like breadcrumbs, weaken your cards to near-nothing (when they're weaker than his for the most part already anyway), and constantly summon multiple monsters per turn when you're lucky if you can destroy one a turn. And apparently, he was just testing you. Yeah.
Marik's dragon, Odion may be one of the hardest opponents in some games. Since his deck seemingly consists of 50%-70% trap cards, you'll be pretty much helpless unless you use Jinzo or some other card that makes traps useless. His appearance in The Sacred Cards is an exception; he has almost no trap cards worth noting in his deck in that game. No, he's That One Boss for a differentreason. In a game where four-star monsters with ATK over 1500 are a very rare commodity barring insane Level Grinding, having an opponent spam monsters well above that including some that hit 1950 without tributes really freaking HURTS.
In Yu-Gi-Oh! 5D's World Championship 2011: Over the Nexus, you and Kalin will face Lawton in 2 on 1. But the thing is he starts with ten freakin' cards and he will burn your LP into a critical amount the first chance he gets. Unless you've got some card that block effect damage, be prepared to lose a lot of life points when it's his turn. Worst case scenario, 7600. In one turn. There's also a 50% chance that Lawton will go first, in which case your computer "partner" Kalin will move after that, likely running into some kind of damage-dealing trap. And then it's Lawton's turn once more before you finally get to play. If you haven't lost by then...
Before then, you'll have to face The Enforcers. Kalin is pretty easy, despite having some few powerful cards. Crow uses an average Blackwing deck, and despite having a solid synergy, his other cards lack the punch. Jack uses some powerful monsters, but you can manage with some destruction Spells and Traps... and then you duel Yusei. Yusei uses a Quickdraw Dandywarrior deck, known for being the top tier tournament deck at the time. While this is a fair one-on-one duel unlike the above, this is halfway through the game, and there's no way you're ready to facing that kind of deck yet.
There's one of the Yu-Gi-Oh! games for Gameboy Advance, where every single one of the higher level duelists have no strategy other than "Use Black Hole/Raigeki to wipe out all your monsters." They almost always have multiple Mirror Forces, Magic Cylinders, Negate Attacks etc. put down. You'll use up half your hand getting rid of their traps and stopping their monsters, finally take something out of their life points... then they play Black Hole and you have to find an entirely new way to get past their defenses. Even worse, they have more than three copies of some cards which you're legally only allowed to have one copy of in your deck.
World Championship 2006 had some really tough Theme Duels, such as the Spell Counter (Use 15 spell counters & win), Dark Scorpion Gang (Use Dark Scorpion Combination and win) and Victory D. (Win with said card) duels.
A few of the Limited Duels were just plain messed up as well, such as No Setting Cards, No Attacks & the dreaded No Normal Summons, since the programming couldn't restrict the cpu opponent to do the same.
In World Championship 2008 we get Speed Guardigan Ferario. The battle consists of three straight duels where he changes his deck every time and you do not get any recovery in between.
Even worse is the set of challenges at the end of the World of Order. While some are easy (use ten traps and win) others are not so much. One challenge requires you to chain five cards in a single chain, but lies and says that you just need to form five chains and win. However, you're required to fight five consecutive duels as the final challenge. As with Ferario, the decks change between each duel, and you are not allowed any recovery other than what was in your deck. The decks are all also filled with Bottomless Trap Holes, Mirror Forces, Dimensional Prison, etc. so summoning a high-leveled monster other than Jinzo (negates trap cards) without Royal Decree (negates other trap cards) is essentially a death wish.
Jaden's storyline in Tag Force 2 gives us a tag duel against Sarina and a mirror image of Sarina. Who are both running Exodia decks that abuse a loop of Card of Safe Return and Manticore of Darkness to run through their entire deck in one turn.
Tea and Mai in Duelist Of The Roses, Tea is the first person dueled in the York Side of the game and despite what you think she's one of the tougher to beat if you underestimate her as her Fairy deck is built around strengthing them and weakening your own monsters.
While Mai has a mountain themed deck and terrain which strengthens her own monsters and if you by some chance at the beginning of the game picked the Zombie Deck to play with you are sol as Zombies lose strength on that field. Not to mention she has a card that disables defense mode and she enjoys getting out Harpy Ladies and Harpies Pet Dragon also which gains strength for every Harpy on the field as well.