So now I really have a roadblock/writers block in what to do next.
I have a few plots out there as well as quite a few NPCs made up to help or hinder the PC's progress. Most of the adventures have been filled with a cheese factor that hasn't been seen since the cheesecake factory's explosion that leveled a small town in Connecticut.
I thought about having them go to some of the forts dotted around Tethyr, maybe to clear them out from others still fighting the civil war. But to be honest, any input from this board would be helpful at this time. I thank you all for your time in reading this.
I hope this helps in some way.
Oh. My. God. ARGH!
I had eleven pages of detailed information typed up. I was describing what type of campaign I'd run in Tethyr if I were in your situation. Then my computer crashed and I lost everything, just as I had finished and was in the process of proof reading. Eleven pages! Gone! ARGH! 
Alright. Well I'm going to keep it brief this time. I'm not sure exactly what type of game you're running or the type of players you have, so it's hard to make a good suggestion. I can only tell you what I'd do in your situation.
If I understand what happened: the players have grown to be ridiculously overpowered and you're having trouble figuring out what to do with them.
If that's correct, then what I think you need is a good villain. Or rather, several good villains.
In my 11 page post that is now dead, I suggested using Shoon VII as a distant mastermind and manipulator of numerous powerful minions. The players would likely never encounter Shoon VII, but instead would be facing off against one of his most powerful minions.
I suggested this minion be a Doppelganger Vampire Lord (Neutral Evil Rogue / Wizard / Arcane Trickster).
To sum things up: This NPC organizes numerous schemes and plots throughout Tethyr. He is supposed to be laying the foundations for the return of the Shoon Empire. Shoon VII has absolute control over this Vampire Lord, but allows him a great deal of freedom in carrying out his task. The Vampire Lord has no idea he serves Shoon VII.
The Vampire Lord would, however, have access to all of Shoon VII's resources. This helps level the playing field between him and the players, if necessary.
The Vampire Lord is a master schemer and manipulator. He's a nightmarish enemy, not particularly because he's super powerful in battle (though he can hold his own), but because he can make the players lives a living hell.
This Vampire Lord is in no way ordinary. He'd have powers similar to a Thrallherder and a Shadowdancer, though they'd be supernatural in nature. His Thrallherder powers are actually similar to Indoctrination if you are familiar with Mass Effect then you know what is being suggested.
In a nutshell, the point of this power is to further extend the Vampire Lord's Domination ability, but at the same time make it more cruel. His Indoctrination method is largely subconscious, though he can control it consciously.
It begins with subtle feelings and whispers in your mind that are difficult to be ignored. Obeying the whispers is re-enforced through feel-good chemicals released in the indoctrinated subjects brain.
Effectively, the Vampire Lord is getting those he indoctrinates hooked on a drug - himself. He is capable of feeding off this, no longer requiring blood as a normal Vampire.
He has absolute control over the amount of indoctrination an individual undergoes. In the beginning, for most (especially those weak of will), it is virtually impossible to detect what is happening until its too late.
As with all highly addictive drugs, those who are addicted want more and are willing to do almost anything to get it. In the end there is a balance that must be maintained between absolute control and usefulness. The more control the Vampire Lord has, the less useful an individual becomes. Yet, the more freedom an individual has - the more free will they're able to exert.
The emotional and psychological damage suffered from indoctrination is severe and permanent. Even if an individual is freed from the grasp of the Vampire Lord's indoctrination (which can be done through a Remove Curse spell or something similar such as Greater Dispelling) it doesn't reverse the damage.
An individual who is freed can suffer from withdrawal symptoms, and the severity of those symptoms would depend upon how much they've been indoctrinated. For those who are lightly indoctrinated it'd be the equivalent of trying to quit smoking. For those who are completely indoctrinated, there is absolutely no hope. They will simply be living husks - vegetables - who, if not cared for, will simply lay down and die. They'd have no mind left, and no will to live without their Master.
All of this would allow the Vampire Lord all the power he needs to conquer a kingdom such as Tethyr.
The goal for him is to become a serious social power within Tethyr through the use of his indoctrination ability combined with his other powers. In my example, I wrote out how he had spent over a year planning his rise to power, and all the things that took place to get him there before the players even arrived on the scene.
In a nutshell, he created a secret rebel group against the Queen, indoctrinating their inner circle. He then indoctrinated a group of bandits who captured the Queen as she was returning to the city. The players go to save the Queen, are given land, titles, and other rewards for their efforts.
However, they've effectively doomed Tethyr with their actions. The Queen is really the Doppelganger Vampire Lord. The real queen is a trophy held in stasis in the hidden and remote secret stronghold of the Vampire.
The players would have been given proper protection from the Vampire's powers through some means (I suggested locating one of Shoon VII's hidden caches). This protects them from his indoctrination ability, but I left it open for the possibility of a player falling under its sway. Basically, I suggested writing notes to the player describing what they felt, and offering XP if they embraced the feelings or did what was desired. They had the option to refuse, but the more they accepted it the further they'd fall under the Vampire Lord's sway - and the more difficult it would become to refuse. (And also the higher the XP rewards would be.) Until, eventually, the player was fully under the sway of the Vampire Lord completely. That was basically my system for dealing with player indoctrination.
The plan was to have Cormyr break out into civil war as the Vampire Lord planned. The goal behind doing this: It helps cover up the Vampire Lord's indoctrination efforts (it makes sense suddenly if people become a bit over zealous in the defense of their Queen), but also to help root out potential threats to the Vampire Lord's rule. The first battles would be designed for the Queen to lose, to give hope for the rebels.
The players would then be required to raise an army and fight on the side of the Queen (who they would most likely be loyal too considering she gave them titles, lands, and rewards). Meanwhile they begin to uncover bits and pieces of information leading to the unraveling of the Vampire Lord's plot.
In the best ending possible the players could get, would be having things devolve into a three way civil war, and helping the true Queen retake the Throne. Various darker endings were suggested, including what would happen if the players decided to side with the Vampire Lord (knowingly or unknowingly).
It was meant to be a hugely open ended campaign suggestion to give some ideas. In the end, the Vampire Lord's greatest strength is his ability to manipulate events and be a serious social power. The players would be required to Outwit and Outplay him while surviving his deadly traps and other obstacles he'd throw in their path.
Since the players are so mechanically powerful, it requires them to deal in more social problems that their uber sword of badassary isn't equipped to deal with. "Oh, that's nice. You're a hero. You saved the Queen. That's great. You still can't carry your uber sword of badassary into the city."
The Vampire Lord can make the players lives a living hell before they ever get near him and be long gone by the time they get to where he's supposed to be. Since he'd be playing all sides against the other, purposefully, he'd have a finger in every pie. That'd give him the ability to use social power to control the options or lack thereof that the players have; requiring them to cut through tons of red tape while he unleashes a lesser evil which they'd be required to deal with right away thus buying him time for himself to carry out his plans.
Of course, then there is the whole bit about killing a Vampire Lord and attempting to make sure he stays dead... especially with a guy like Shoon VII who might want to bring him back in a decade or so after his defeat.
For more information on Vampire Lord: www.wizards.com/default.asp?x=dnd/mm/200...
So yeah. That's my suggestion. Hopefully you find something useful in it.
And awesome ideas Meldread!
The Pcs aren't overpowered too much. I'e been fudging some rolls to keep them alive. I was going to have them fight a green dragon CR5 I do believe, and they almost killed it with ease. So I put them against two of them at once...if the breath weapons wouldn't have recharged so quick it would have been a fair fight!
This time around, I'm the DM. Our regular DM rarely let us get the jump on any encounter, we were mostly the ones surprised....so I guess I'm letting them get away with a few things, but nothing broken. They just reached 6th level after the two dragon encounter and our about to be on their way back to the capitol.
They've saved the princess in typical cheese fashion from a kidnapping attempt so I might use the doppleganger queen idea. They have met her once, and maybe one of the characters can find something wrong with her.
Ah. When you said, "Most of the adventures have been filled with a cheese factor that hasn't been seen since the cheesecake factory's explosion that leveled a small town in Connecticut." I thought you meant cheese as in: "My players are using characters that are extremely optimized, highly powerful, and bordering on broken."
Taken into context, I thought you were having trouble figuring out ideas on how to challenge them. If you're having to fudge dice rolls then it doesn't seem as if you're having that type of trouble.
That being said: What I suggested might be a bit much (or way more than a bit, really 
) for them. However, Doppelgangers are awesome, if played properly.
It's unlikely that a Doppelganger is going to try and impersonate someone of high power and then suddenly act radically different in such a way as to be easily noticeable. Especially the Queen. Meeting her once likely would not be very helpful, though individuals extremely close and intimately familiar with her could potentially spot that something is off.
Assuming the Doppelganger didn't have the ability to Mindrape the Queen (learning everything that the Queen knows - thus enabling the Doppelganger to impersonate her near-flawlessly), or doesn't have someone who can assist him in the matter... then the Doppelganger has likely spent months, if not years, close to the Queen (most likely as a trusted servant), learning her mannerisms, learning her speech patterns, learning about her various relationships (particularly with those intimately familiar with her)... all before the Doppelganger acted to attempt to impersonate her.
It is exceptionally hard for a Doppelganger to easily impersonate such a powerful and important individual. Thus, most Doppelgangers impersonate individuals that society doesn't really care about (beggars, prostitutes, etc.), or they attempt to forge their own unique persona. Alternatively, they'd also target powerful individuals who are more recluse, and thus don't have many intimate relationships (reducing the chance they'd be caught).
As a general rule, Doppelgangers make awesome spies and assassins.
There was an attempted assassination/kidnapping of the queen's daughter that the PCs stopped prior to leaving for a recently completed adventure. They come back to find that one of the suspects has been killed in the dungeon by a normal blade through the gut, no poison, no suicide, no magic. I'm not going to disclose who the doppelganger is but I will give them plenty of people to suspect.