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. Oh, and if you're planning on boosting your life points to stock up for the last fights? So sorry. The game rounds down whatever life you had to 10000 for each fight, but never rounds up.
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 Yu-Gi-Oh! The 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 Yu-Gi-Oh! 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.
Spirit Caller has Dark Zane, or Zane after he flipped his shit. Dark Zane is this mixed with luck based boss because matches with him end up in one of two ways: you steamrolling him or him steamrolling you with his Chimeratech OTK deck; which you can lose against if you don't have a good hand ready to take his machine out. Dark Zane is also a shadow duel which can mean game over if you cross him while spirit hunting.
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 (Keep in mind that losing against any of those people will not force you to retry again, unlike the above).
In World Championship 2004, 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. What's more frustrating is that World Championship Tournament 2004 has a "luck" system where the AI will immediately draw these monster destruction cards if it starts losing, ensuring the player cannot keep a powerful monster on the field for long.
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 Ferrario. The battle consists of three straight duels where he changes his deck every time and you do not get any recovery in between.
Later on, there's Sky Guardian Sefolile, which is the same thing, but FIVE duels in a row.
Jaden's storyline in Yu-Gi-Oh GX 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.
Pairing up with Viper in Tag Force 3 is a nightmare, because his A.I. is one of the dumbest in the game. If you only have one venom monster to defend you and the trap card "Offering to the Snake Deity" is set, he'll use it as soon as he can to blow up your only defenses and take out two of his. In short, he's not a big picture thinker, and he will frustrate you with his playstyle. Furthermore, the special duels (boss duels all players go through when selecting a partner from the "Partner 2" category) he goes against are all painfully terrifying. Crowler and Tyranno can overpower the venom monsters and blow up your Venom Swamps, Atticus and the Gravekeeper can swarm and disable graveyard access to Vennominon, and Amnael/Adrian are likely to remove your monsters from play, screwing up Vennominon from utilization.
Pairing up with Fontaine presents similar problems but on a different reason. Her deck isn't horrible, per say, but it has no sense of timing. She uses a Simochi deck which revolve around using bad reaction to simochi/nurse reficule the fallen one to deal the gains as damage. But as the AI doesn't use the cards in the correct order, she'll end up giving the enemy more lps than she would deduct. Not helping matters is that cards needed to support her are in a pack that's difficult to unlock in its own right.
In Nightmare Troubadour, there were several tough duelists, but the hardest fight has to be the boss rush of Big 5, Noah, and Gozaburo. Gozaburo uses an Exodia deck with very little strategy and weak cards, so he's no threat at all, despite what the game says. No, the major problems are Big 5 and Noah. Big 5 uses a deck centered around Satellite Cannon, which is an annoying one-Tribute monster that cannot be destroyed in battle by any monster Level 7 or lower, and increases its attack by 1000 every turn, which then drops back to 0 once it attacks. Big 5 will keep Satellite Cannon in Defense position until it has several thousand attack, and then he will kill you with battle damage. If you somehow manage to defeat Big 5, you are faced with an even tougher opponent: Noah, with his fairies. Noah plays many powerful fairies and backs them up with The Sanctuary In The Sky, which eliminates all battle damage with battles attacking a Fairy-type monster. The major problem with Noah, though, is his ritual monster Shinato, King of a Higher Plane. This guy has a whopping 3300 ATK/3000 DEF. So you'll just Set monsters until you get something to kill him? When he destroys a Defense position monster, you take Effect damage equal to that monster's attack. Good luck killing this guy.
In Duel Transer, Odin's first encounter in story mode can become a major roadblock. Using a Water deck that excels at both beatdown and returning monsters to the hand. Chances are, by now, the player has built a deck that is reliant on Synchro Monsters, which are instead returned to the extra deck instead of the hand. And the numerous powerup effects of Spined Gillman and Umiiruka can make the deck incredibly challenging to face. If that isn't enough, Odin's extra deck includes Brionac and Trishula, who are staples of the limited/forbidden lists following the production of this game, but usually his non-synchro monsters will be powered up enough to force the player's synchro monsters into play, where the bounce effect can come into play. Thankfully, by the time the player has to face this boss again, who is now more powerful, the player will have access to more cards, which will make this less of a challenge.
Tyrant has the Epic Siege on Kor raid. The commander summons a Rat Catcher every turn, which can immobilize you and Phase you as well, blocking that unit from being affected by your own friendly activation skills. The core structure cards are some of the deadliest in the entire game, including the Cannon Wall, which has 15 health, and in 3 turns it Enfeebles all of your units, making them take 2 additional damage from all attacks and then proceeds to Strike all of them for 3 damage (after the effects of Enfeeble). There's also the Cluster Mine, which has Counter 10, which will pretty much kill any of your units that hit it. You think you can just Siege away those structures? Well, it also has two of its own version of the Gatling Tower, which will Strike one of your own units for 4 damage, inflict Chaos on all of your units, turning all of your own attack skills against yourself and thus blocking any Siege strategy you might employ, and Sieging all of your structures for 2 points of damage, all after only 2 turns. If that's not enough, the randomly generated player-available cards can make it even worse, including the Metalworks, the Usial, and Orwold's Reckoning, all of which can summon even more enemy units in addition to the commander's Rat Catchers. The best possible deck for this raid has only a 77% win rate, while all other raids have at least one deck with a 95%+ win rate, and it has 1.2 million health which requires great contribution from all 40 possible people to take it down within the 3-day time limit.