Well, since I'm writing this in my journal, so I'm talking about my biased personal preference in a "satisfiying puzzleshipping story", so please don't take offense if my kink is not your kink. Normally when I think about an epic story, the first thing come to my mind is PLOT. PWP and character monologue over a certain event could be entertaining to read, but to get into the top of my favorite list, it has to have a plot. So what I'm going to ramble about are all about stories with plot. Also I'm allergic to infinite woe, and tragedy often leave me in an emotional break down for days,so I usually prefer stories that have more action than angst or are emotional balanced and fairly happy. Now I suppose it's safe to start.
1) Stories that follow canon:
canon is amazing, and there are more hints of puzzleshipping than that of any other pairing. Their relationship is fascinating, with the two shared a connection, a body. They went through all the hardship together, forming an unconditional trust in each other and always rely on each other to overcome any obstacle. So why it is so hard to write a puzzleshipping story that follow canon? Now lets divide it to three commonly used timeline:
a)Post canon:In the canon, the pharaoh left for the afterlife. It's almost impossible to have puzzleshipping, unless you either (1) bend the canon so that the pharaoh stay or (2)come back from the afterlife.
In the case of (1) I have been mulling over it actually. I admit that having the pharaoh leave for the afterlife is the best way to end the manga. Since the pharaoh was a spirit, not going to the afterlife would mean trapping him inside a golden trinket for eternity. But actually, the Pharaoh could stay, for a while at least. Ishizu has never mentioned any specific date limit in which the Ceremonial Battle could be performed (correct me if I'm wrong), so it could be performed anytime the Pharaoh feel like leaving, as long as Yugi is alive. Of all the fics I've read, only one I see following that logic and have a spirit Yami staying with Yugi. But even then, it's hard to develop a plot from there because they have beaten all the evil and got the pharaoh's memories, to continue putting more villain would make it as boring as the spin-off R (I'm sorry if you are fan of it) . The fic I mentioned having Yami staying as a spirit developed it to a time travel, in which the consequence of the pharaoh delaying his departure is Yugi being thrown back into the past to fill in for a mission even before Zork, and damn was it good. One of the best I have read actually. There are some other stories that have Yami staying with Yugi with a body after Ceremonial Battle, but most of them are not convincing. Also, since the Pharaoh got his own body, it often develop to (1) a high school romance cliche (2)A fight against a new villain, in which the Pharaoh do all the jobs because he had his body and Yugi become useless (3) a dreadful Yami-and-the-gang-ignore-Yugi, all of which are not appealing, at least to me.
In the case of (2), it take talent to make the whole dead-people-come-back-to-live buyable, and also it's also important to develop a plot: why/how did he come back? for what purpose? because something are at stake, a new mystery or just because he want to? was there a price of his coming back? What is the role of Yugi in this?How does it end? It's a whole brain wrenching process and I only found few fics that fulfill all the answers.
b)Begining/halfway of canon: There are also two common ways in this timeline: (1) Write events that follow canon but change parts of it, and (2) Just follow it to a specific point then bend it to a completely different direction, in which you make up all the event to the end.
In (1), it's hard to keep reader's interest, because readers already knew all the event if you keep it till the end.
In (2), it's very interesting but also very hard. To write all the events and your own satisfying ending, which have to be still keep the manga's atmosphere but still puzzleshippy-ish is very very hard. The only story that did this perfectly is Sight the king by Olesia, it's amazing, with a very unique plot but still manga-like, has a lot of creative games and the characterizations are very canon but also very puzzleshipping. It's my most fave story of all time, she is a total genius!
c) Time travel: This! This is my personal fetish, with a modern Yugi Mutou and Pharaoh Atem in ancient Egypt, it's total love. It's also a very convincing situation for Yugi to develop a relationship with a solid Pharaoh. So what is so hard about it?
(1) It's time travel: It's a situation where one word about future could change the whole history. It's delicate. It's super hard to play with time paradox. Even some of my most favorite time travel stories couldn't fully cover it.
(2) It's Ancient Egypt: The custom and attitudes of characters have to be done carefully. In Yugi's case, there must be awkwardness about the different culture, there must be disbelief if the time travel is not intentional, there must be some discreet, since even though Atem is the Pharaoh, he is partly not the Pharaoh he knew. About the Pharaoh and his court, there should be the doubt, they also have to show authority and demand respect. About the Pharaoh, I personally like him to act..more king-like, not like a horrible tyrant, but someone with the unwavering belief in justice and a bit..arrogant, who demand everyone to respect him like a god he is, Yugi included (at least when they first meet). Stories where Yugi acts all calm about the time travel and immediately adapts to the culture change, spilling everything about the future first time round; the court totally believe him and welcome him with open arm, Pharaoh Atem act like a saint... is just unrealistic, and stories where Atem and his court act like a bunch of teenager boys just make me facepalm.
(3) It's canon, the fate of the pharaoh is mostly sealed: There are plenty of timeline and ways the time travel could occur, Yugi could go to the time travel from during or post-canon, he could go to the timeline before or during the time Zork occurred, but planning a plot for this is no easy feast. If it happen before Zork, the ending need to be planned carefully since the pharaoh get sealed in the end and it's super hard to get a convincing happy ending. If it's a rewritten of Zork incident with Yugi in it, the fate of the pharaoh also have to be considered carefully, because if the pharaoh didn't die, the puzzle would most likely not get in to Yugi's hand and the time travel would most likely not occur and we get into a crazy circle of timeline error.
Time travel is fascinating, but it's also very dangerous to play with. To develop a good plot to go with it is another brain-wrenching process, and I admire whoever could pull it off.
2) AU stories: AU is basically the most convenient thing in the world of fanfiction. With this you don't have to worry about canon boundary, the fate of the pharaoh and whatnot. You can give the Pharaoh his own body and hook him up with Yugi, isn't that convenient? So what is so bad about it?
The connection, the experience they both went through, the companionship, the trust....basically everything that are fascinating about their relationship, they are thrown out the window.
An awfully huge price for a body, isn't it? (now I'm almost tempted to write a story about Atem getting a body in exchange of everyone's memories about him, but I can't get out a stable enough story for it, and I fear it would be angst ridden, so this idea is open for anyone who is interested to pick up)
So, to fix up the down side of AU, there are some ways people often approach:
a) Create another plot to rebuild their companionship: make a plot to throw them together in a quest to overcome some obstacles, mystery.. etc, at the same time build up a relationship, to create something that is close to canon between them. It's very important to put them up in equal ground, give each of them a role, not just one protect another. Yami protect Yugi is cute, but it get old fast.
b) Approach their relationship from a different angle: in which they are not companion, but could be from rival and enemies to romantically couple. Personally, I liked the first than the later. I feel the puzzleshipping relationship is too sacred to be something mundane like a couple of love interest, especially with all the love drama cliche like abuse, rape, cheating, pregnancy, jealously... that the fandom is so fond of. There are some romance I find cute, but they are rare.
Basically, AU puzzleshipping can be easier to write than canon, but to built up a good story is still a very hard thing to do. It's all depend on the creativity and writing skill of of writer.