One of my campaigns started in Kitsunemori (Japanese inspired, all characters are humans) with some self-written material, moved into Barrow of the Forgotten King (finding the Weapon of Legacy in an old tomb) and Red Hand of Doom (Hobgoblins and Dragons invading), and will soon be reaching the end of Red Hand of Doom.
One of my players was interested in a Weapon of Legacy – she wished for a sword of light, and so we introduced a flaming sword that has abilities to be unlocked at levels 5, 10, 15, and 20. Red Hand of Doom also features an aspect of Tiamat CR 13. I also bought City of Brass (Necromancer Games) and hope to receive some Planescape material soon. Based on this, I'm trying to weave an interesting story and would appreciate some ideas for where to take it, what worked for you, warnings of pitfalls, and so on.
I've been talking to my players, and basically they're a bunch of powergaming butt-kicker tacticians, except for the player with the Weapon of Legacy. I think this is excellent, because I can focus the plot on the Weapon, and the others will just come along for the fight. I've asked five out of six players and they all agree. And finally we'd like to play this campaign up to level 20.
Here's the backstory for the Nodachi (greatsword) called Attaxa, with some ideas of where I'm heading:
About a thousand years ago a valiant knight from Celestia used the sword to kill an old evil god of a forgotten race in Dis on Baator's second level. [Any ideas for the knight? Does this make sense? At this point in time Attaxa is a light sword – whatever that means, I haven't figured it out yet. Amaterasu is the LG goddess of the sun.]
On the way back he was killed by Tiamat on Avernus near the skull tower and the sword was lost. Apparently Amaterasu's light was bound in steel and brass. [Magic weapons get weaker away from their home plane; I thus wanted the dragon to send the sword to the swordsmith masters in the City of Brass, binding the light and turning it into fire. This explains the current state of the sword and offers a way to undo it eventually. Haven't got much more than that.]
A Baatezu used the sword on a Prime against an aspect of Pazuzu, the lord of the Tengu (evil bird men). The battle was lost and Attaxa was claimed by the Tengu kings. When they allied themselves with the human empire of the eastern mountains in their fight against the fey of the swamps that covered the area of Kitsunemori a hundred years later, the Tengu lords presented king Ueshiba with the sword Attaxa. The demon lord Obox-Ob had built an empire ruled by Kappa (turtle demons) and Kumo (spider demons). The war was won and when Ueshiba died, the blade was buried with him. [This explains why the blade was buried with the king. It offers the potential of a sidequest to visit the Tengu eeries and some Obox-Ob, turtle-, or spider demon action.]
In terms of mechanics (all bonuses relative to the current bonus on the Material Plane) – I was planning to have the light sword be at +2 on Celestia, ie. +0 on the Material Plane. The transformation in the City of Brass changed the "home plane" of the sword. Now it's +2 on the Inner Planes (the City of Brass is at a junction of fire, earth, and air) and -2 in Celestia. Undoing this will make the sword -2 on the Inner Planes, unchanged +0 on the Material Plane and +2 on Celestia. [But why would anybody want to change the sword thusly? Plus: How did the sword end up here? Did Tiamat send an agent with the sword here? To do what? Was the Baatezu that ended up with the sword in her service? What was he doing fighting Pazuzu on the Material Plane?]
As you can see, I have some ideas but I need more "glue". I think I'd love more plot secrets to allow my storyteller character moments to shine. She is important. She protects & saves. She figures things out and intuits who her friends and foes are. The others want interesting fights, cool treasure, and they like discovering that they are being betrayed and outwitting their foes at the last moment.
Help me brainstorm a cool campaign taking them from level 12 to 20. 
Kensanata wrote:
Well two heros spring to mind:
One is Momotaro (aka Peach Boy) from traditional japanese children story. He was found in gigant peach by eldery couple without children as gift from gods. Soon, when he grew up a bit he was sad to see his country rawaged by oni king and his horde so he set on adwenture. In his trawels he found 3 companions: Wolf king (or Dog king, depending on wersion), Monkey king and Falcon king (they could be Animal lords in disguise), who agreed to help him in his quest for redicuously small price of Kibi Dango (rice cake). Anywas, in the end they have defeted oni king and his hordes who swore never to pillage again. After that the valiant four had many more adventures, who knows maybe the trip to Dis was one of them.
Second idea for your knight is inspired by character by manga founder Osamu Tezuka.
The character of his horror manga is caled Hyakkimaru (manga is named Dororo by Hyakkimaru´s tiefing sidekick), he is samurai who was as child mutilated by demons/devils who each took parts of his body as power amplifier (one took eyes, other arms etc...), Hyakkimaru would have died, but he was sawed by genius artifisher and medic who created him new prostetic body of metal and wood, filled with warious gadgets and weapons. Equiped like that he set on wengance quest to slay demons (or devils) and retrive his body parts. But there was catch: with each new body part he gained, Hyakkimaru beocome more and more human, but he also became weaker and weaker becaouse he was losing his artificial parts.
He could hawe gone to Dis to retrive one of his parts body parts from those ancient devils nobles.
That´s it for now, hope I was of any help to you.
BDW, I realy like your idea of using Abysal Lords as Yama (demon kings of oriental legends).
One-eyed, one-horned, flying, purple people eater says: "Monsters are nature's way for keeping XPs fresh."