As I said, I was speaking from personal experience. I'm sure others' experiences have been different. It bears pointing out that the characters that this players compares himself to are very optimized, and there are considerably fewer optimization options for the executioner than a rogue or paladin.
We're 5th level, and while the average damage with an at-will is comparable (13 for both the executioner and paladin, 16 for the rogue), the executioner has one, perhaps two opportunities per encounter to deal roughly twice normal damage (with poison or the assassin strike). The rogue and paladin usually have three opportunities per encounter to double or (in the case of the paladin) triple their normal damage. The biggest issue for this player is the lack of encounter powers, which will only get worse as the party gains levels.
The executioner is a mechanically weak striker. But seriously? A 1st level executioner with a Dex of 18 and wielding a rapier will do 2d8+4 = 13 average damage on a melee basic attack. A 1st level Rogue with, a shortsword, a Dex of 18, and a Cha of 14 will do 3d6+4+2 = 16.5 average damage on a Sly Flourish with Sneak Attack. Both with no special weapons or feats.
Neither Rogue nor Assassin are optimised in the slightest - they are doing damage equal to
average first level characters there.
The Paladin's more interesting. With a Str of 18 and a two handed (d12) axe, at first level he should be doing an average of 10.5 damage per hit. A +1 weapon (as any fifth level character should have) will bring him up to 11.5. Axe Expertise for 12. And Weapon Focus for 13.
He still isn't a hard-line optimised character. Two feats and a two handed weapon is all.
Let's do a little obvious optimisation starting with a Thief.
Dex 19 (meaning 20 at level 5). Melee basic attack with shortsword is now 1d6+7. With Sneak Attack that makes 3d6+7.
+2 shortsword, Bracers of Mighty Striking (L2 common). We're up to 3d6+11 damage on a melee basic attack with combat advantage (which we should always have thanks to tactical trick).
Backstabber feat and Light Blade Expertise. d6+2d8+12 damage on a melee basic attack with CA.
I still have a feat to spare and my racial abilities (or two feats for a human) and I'm doing 24.5 average at will damage with Tactical Trick (rising to 26.5 with Acrobat's trick assuming CA). Yes, Backstab doesn't double my damage output - does it need to?
I'm also curious how the paladin gets +26 damage twice per encounter. For that matter I can think of few rogue powers that do +16 damage. And are you remembering to drop the low-hp monsters with the assassin? (It helps to think of powers like garotte strangle as encounter powers).