firesnakearies
Explorer
In general my advice would be to throw away the encounter design rulebook. A standard challenge is now +3. +5 encounters are now the difficult encounters (as long as the creatures and enviroment are designed properly).
I would seriously consider redesigning all the monsters the PCs fight, or at least making an assessment of their damage (and increasing it), also like you said giving all creatures an actual critical damage is a very good idea.
This.
Epic characters are crazy tough. Really skilled 4E players with well-built characters are crazy tough at any level. Combine the two, and you've got unstoppable killing gods against any standard published encounters.
Go nuts with encounter design. I'm consistently shocked by how much stuff 4E PCs can handle.
For example, a friend of mine and I are playing through the E1-E3 series. Two of us. The DM was running it as written, an adventure designed for a five-PC party, and we were mauling it with only two PCs. (A Warden and a Sorcerer, no leader!) So about halfway through E1, he actually started adding stuff and making it harder. He turned the final encounter of E1 into a level 29 encounter for a group of five. We were level 23, and again, there were only two of us. We still demolished it with ease.
As DM, I've thrown stupidly big encounters at my PCs, and they've pulled it out. I've had them fight 13 battles (all above their level) in a day without an extended rest. I've had them fight 17 non-minion monsters all above their level at the same time. (And these were LOW level characters, too.) I add tons of minions to already hard encounters without even counting them into the XP budget. The PCs prevail. It's amazing.
If you have good players with strong characters, at epic levels . . . take off the gloves. Just go crazy, they'll be fine. The encounter building guidelines and published encounters seem aimed at . . . well, pretty mediocre players, in my experience. Don't be afraid to move beyond that, if your PCs have proven themselves to be superhuman.