OK, it seems my statement about characters being lucky to do 20 pts of damage bears some qualfiication.
I'm referring collectively to the damage output from the parade of characters I've seen within the half-dozen 4e parties that I've played in, ranging from levels 1-12, of which only a few have been tricked-out rangers and rogues (and that fighter doing +26 damage per hit is conspicuously absent altogether). If encounters were built using 3e's design of a 1-monster/4-players ratio, I could see only focusing on characters whose role it is to close down opponents and just not counting the healers and buffers and mezzers and meat shields.
But 4e's design is 1-monster/1-player, with all classes designed to contribute damage. Now you ought to count everybody, not just the total badarses. And yeah, some of those characters roll single digits on damage with rather alarming frequency.
I'll certainly admit that not every character will be regularly dealing out 20 damage, and that super-optimized characters should be used as the baseline - but that is still a very different story than your original claim, which was that 20 damage was rare for non-daily powers at heroic and paragon levels.
Now, I'll also note that average damage is a different thing entirely - but your original discussion was about damage dealt when people hit, so that is what is being discussed.
Any Rogue and Ranger will be dealing over 20 damage with Encounter Powers in the Heroic tier. Many Rogues and Rangers will be dealing over 20 damage with At-Will powers in the Heroic Tier.
(Rogue, with Dex 18, 2W Encounter Power, +2 Weapon, Backstabber: 2d8 (Sneak Attack) + 2d4 (Dagger) + 4 (Dex) + 2 (Enhancement) = 20 damage.)
(Brutal Rogue, with Dex 20, Str 14, +2 Weapon, Backstabber, Weapon Focus, At-Will Attack: 2d8+2 (Sneak Attack) + 1d4 (Dagger) + 5 (Dex) + 2 (Enhancement) + 1 (Weapon Focus) = 21.5 damage.)
(Ranger, with Dex 16, +1 Weapon, 2 attack Encounter Power: 2d10 (Longbow) + 1d6 (Quarry) + 6 (Dex x 2) + 2 (Enhancement x 2) = 22.5 damage.)
(Ranger, with +2 Weapon, Weapon Focus, Twin Strike, Lethal Hunter: 2d10 (Longbow) + 1d8 (Quarry) + 4 (Enhancement x 2) + 2 (Focus x 2) = 20.5 damage.)
Fighters, Paladins, Clerics and Warlords with two-handed weapons will be dealing over 20 damage with Encounter powers in the Heroic Tier.
(Str 18, +2 Weapon, Maul, 2W attack: 4d6 (Maul) + 2 (Enhancement) + 4 (Str) = 20 damage.)
Warlocks have a harder time of it, but can deal over 20 damage with At-Will powers when those At-Wills deal the full effect. (Dire Radiance and Hellish Rebuke being triggered.) Most Encounter Powers will deal almost 20 damage - or more, from an optimized Warlock.
(Con 18, +2 Implement, 2d8 damage encounter power: 2d8 (Power) + 1d6 (Curse) + 4 (Con) + 2 (Implement) = 18.5 damage.) Higher Con and a feat pushes it to 20.5 damage.
(Con 18, +2 Implement, Dire Radiance or Hellish Rebuke triggered: 2d6 (Power) + 1d6 (Curse) + 8 (Con x 2) + 4 (Implement x 2) = 22.5 damage.)
By Paragon Tier, pretty much everyone's Encounter Powers will be dealing over 20 damage when they hit.
Any melee characters with a 1d10 or bigger weapon: 2W + 2 (Weapon Focus) + 5 (Primary Stat) + 3 (Enhancement) = 21 damage.
By Paragon Tier, pretty much every Striker's At-Will Powers will be dealing over 20 damage when they hit.
Warlock At-Will Eldritch Blast: 1d10 (Power) + 5 (Primary Stat) + 3 (Enhancement) +2d6 (Curse) = 20.5 damage.
Rogue At-Will: 1d4 (Weapon) + 3d6 (Sneak Attack) + 5 (Primary Stat) + 3 (Enhancement) = 21 damage.
Ranger At-Will Twin Strike: 2d10 (Weapon) + 2d6 (Quarry) + 6 (Enhancement x 2) = 24 damage.
Stating that it is rare or lucky to be getting Quarry/Sneak Attack/Curse damage is absurd. Sure, it might not happen every single round, but it should definitely be present the vast majority of the time. If not, perhaps something else is going horribly wrong.
Even if you are looking at the damage of the party as a whole - the non-Strikers aren't that far behind. As mentioned, any characters with two-handed weapons are looking at being in the 20 damage range with encounter powers. Those that aren't - casters like Wizards, wisdom-based Clerics, etc - are often using powers that are hitting multiple targets, thus boosting them up into that range as well. (And single target Encounter powers are still doing around 15 damage, which isn't far off.)
As mentioned elsewhere, average-damage wise, you might have a point. But the quote that started this said: "In 4e, you're lucky to see a non-daily attack do 20 points of damage, even at paragon levels."
And that is only true if the party has no strikers and uses no encounter powers. That seems... unlikely.