Having spent a good bit of time in the realm of Uber stalling, I can tell you that Deoxys-L is one of the best defensive Pokemon in the whole game. With a movepool easily larger than Clefable's (it has access to moves from all 4 forms) and defenses like that it's the ultimate Spiker. Its ability to Toxistall is so great it can take on whole teams at once. Deoxys-L is a defensive beast.
Deoxys-E seems a lot less impressive. Base 95 offensive stats may seem average, but keep in mind that he's outspeeding most Choice Scarf users already and that you can just put Choice Specs on and he becomes too dangerous. If your team doesn't happen to be carrying a priority move (in other words if you're running a stall team or if you're unlucky) then you're basically screwed.
One thing people don't understand is that most Ubers aren't completely and utterly game breaking. But when you think about how they work in OU, you realize that the metagame would have to change to counter one Pokemon. If that's the situation, then that Pokemon should stay in Ubers.