From experience I would say that a true solo (one by itself) should be 3 levels above the party to constitute any real threat. At this level it can take a little debuffing and still maintain a reasonable chance of consistantly hitting.
Once you get to Paragon tier every Solo should be designed with one eye on removing status effects. Care should be taken to make them thematic or reasonable for the creature in question, depending on their power these anti-status effect abilities should also have a draw back.
possible examples:
Minor action: creature deals itself 30 damage to remove any 1 status effect
Free action: creature gains a saving throw against any 1 status effect but takes a -4 penalty to attack rolls until the start of its next turn
Standard action: creature makes an attack vs. Will or Fortitude; on hit it deals [medium expression] damage and transfers any 1 status effect from itself to the target
Immediate interrupt (when targetted by a stun effect): creature makes an attack vs. Reflex or Will against attacker; on hit both creature and attacker takes half damage and full effect of the stun, if either party breaks the stun both are released
I think when it comes to penalties, only the greatest penalty should apply. None of this Vicious Mockery (bard) + Maze of Mirrors + Psychic Lock (illusionist) + Ride the Giant Down + mark (warden/giant slayer).
Yes, I checked with my players, and that actually was all active on the dragon one round. It ended up being -11 to the first attack roll, -9 thereafter, with an extra -2 if I attacked someone who wasn't the warden.
But since my dragon got away, and is supposed to be a powerful necromancer/sorcerer, I intend to have some fun. The party will probably wait at least half an hour so they can sit down and cure disease on the two PCs who have "djinni's leprosy" (mummy rot), which gives me time for the dragon to set up a hallucinatory creature version of himself to draw out at least a few attacks.
If the party withdraws to take an extended rest, well, I'll just have fun. Don't mess with cursed desert necromancers.
In my games, we're working with a rough house rule of typing penalties:
Power: A penalty inflicted by a power (e.g. Illusionary Ambush)
Mark: A mark
Feat: A penalty inflicted by a feat (e.g. Psychic Lock)
Item: Item inflicted penalties
So far, this scheme has worked pretty well to make sure that the Bard (Vicious Mockery), the Wizard (Illusionary Ambush), and the Paladin (Enfeebling Strike) aren't all stacking penalties on the marked creature.
I feel your pain, dude. I hand crafted this monstrosity 8th-level solo for my 5th or 6th level party (been a while, can't remember). It was The Gnoll Queen, she rode a cacklefiend hyena and had 2 of those level 5 or 6-ish gnoll soldiers helping her. Hitting for around 4d6 + 12 or something obscene. 6 PC's. This fight was supposed to be the hardest thing they've ever encountered.
And...it was a total flop.
I had some siege engines on fire as scenery that I wanted her to use to throw PCs into. Turns out, she was the one getting thrown into them and held there while stunned or dazed, marked, immobilized, slowed, etc. It was awful.
I hope these new solo design guidelines help things.