While Deoxys-S is one of the few Pokemon in OU that is guaranteed to do its job well, I feel it isn't Uber. From what I've used, faced and observed, Deoxys-S is unable to consistently provide suitable conditions for my team to have an easier sweep to the extent at which some people here are saying. Deoxys-S will guarantee you Stealth Rock, unless they run a Prankster Pokemon with Taunt. While you could use Mental Herb or Magic Coat, it's more likely you'll be running Light Clay, Focus Sash or Taunt. I feel personally, that Deoxys-S without Taunt is easily bait for something like Dragonite to set up.
Before I talk about Deoxys-S, I'd like to talk about my experiences with it. For me, Deoxys-S has been a fantastic Pokemon when used on the ladder, and while my current ranking doesn't show it, a simple Hyper Offense team of Deoxys-S and 5 Physical Sweepers has gotten me to #4 on the ladder with roughly a 1540 rating. When people build their teams, they don't take Deoxys-S into consideration, perhaps because it isn't visually a Pokemon that can cause harm to a team. I agree, and usually it isn't something that is in the back of my mind that I need to prepare for, however, I personally have little problem with Deoxys-S leads, unlike October 2008 when it was becoming increasingly clear to some that Deoxys-S was Uber. One reason for this is the advent of Team Preview. Team Preview is there to be utilised, and I stress this with every tutee I have. Some people just rush in, and don't use Team Preview to their advantage, not being as careful as they should (and I am guilty of this when I'm in a ladder grinding session), and I think this is more evident on the ladder, where people are trying to cover as many games in as short of a time as possible without really thinking. In tournament games, good players have a good idea to what to do vs Deoxys-S, planning a couple of turns ahead to what Sweeper is going to come out right after Deoxys-S faints. They're more cautious for obvious reasons. Admittedly, the HO team I've been using has an average record for me in tournaments, and practice games vs good players trying out teams for different tournies. Not to say I'm a terrible player, but I feel the HO playstyle is definitely more suited for ladder play against the masses, than anything else.
Onto Deo-S itself, I think that the Dual Hazard Deoxys-S lead is a positive influence on the metagame. Non-hyper offensive teams have the option to opt for a good hazard layerer, without having to resort to something bulky such as Ferrothorn or Skarmory, and I feel this enriches variety and creativity, by encouraging offensive teams with more frailer Pokemon such as Infernape to become useful, without having to slow down the tempo. If your team is destroyed by DD Dragonite after your counter has taken SR and Spikes Damage, then the problem is Dragonite, or the fact that you have built your team poorly, or the fact that you underestimated the sweeping potential of probably the best Pokemon in OU.
Deoxys-S provides a different approach to setting up hazard damage, a different playstyle. Ferro will almost certainly get up SR/Spikes in 90% of games and also have other use; it punishes for Spinning on it, and it can KO Starmie and Donphan with a STAB Power Whip. Tentacruel has to hope it burns it with Scald. While Deoxys-S likely will die early on, Ferro will plough on until the mid-to-end game, bit by bit accumulating hazard damage. One reason why this is seen as more acceptable than quickly getting 1 or 2 layers and then dying, is that it is more drawn out, and the 'impact' (excuse me if that sounded cheesey) of the situation that your team might possible get swept is dulled.
On the subject of spinners, I agree that they all are pretty bad, except for Tentacruel who is one of the most difficult Pokemon to face in Rain (from experience), and Starmie who usually gets off a Spin.
A quick note regarding the LO cleaner set: The LO Cleaner set is uncommon and practically unheard of, and judging from the sentiments in this thread, people are split on both leading sets, and not this one in particular. While something doesn't have to be used much to be Uber (Gen 4 Wobb), I have not seen a single complaint regarding the LO set in any IRC channel I frequent, nor on the PO chat. Summaries of why it's fine in OU have already been provided within this thread by other people and are pretty sound.
The following logs are of me using my HO team against some people. I didn't play amazing in any of the logs, but I did win in all of them. What I would like to point out is that Deoxys-S was not the key deciding factor in any game, infact, it was the sheer power of 5 very strong sweepers breaking through the opponent's team and therefore winning me the game:
http://pokemon.aesoft.org/replay-free-candy-vs-Nachos--2011-11-02-private671859685
http://pokemon.aesoft.org/replay-Nachos-vs-ITAEden--2011-11-15-private799603113
http://pokemon.aesoft.org/replay-Nachos-vs-Ojama--2011-11-07-private1553329492
If I had to place the blame on Deoxys-S or the amount of strong set-up sweepers BW has introduced, then I fully believe it rests on the individual sweepers themselves, rather than Deoxys-S.
I agree with PK Gaming that the Dual Screen set is annoying. Sometimes I forget it too, but the screens don't last forever. However, 'annoying' does not equal broken. A ban should be reserved when something is pushing it to the limit, and Deoxys-S hasn't reached that limit. The Dual Screen will not always be successful, most of the time you'll be getting up SR and a screen, but not usually both. From here, you can exploit the weaker side of the team through sending in something strong. Although this is biased towards Special Sweepers, as Deo-S usually sets up Reflect for all the Physical Sweepers, something like Latios can really cause pain, considering most set up sweepers start off slower than it. Starmie is lame to face as well.
Overall, I believe that there is more of an underlying anger under the 'cheapness' of easy-to-use HO teams, rather than Deoxys-S. kd24 mentioned that Deoxys-S is a perfect Pokemon to bait something like Scizor in, only to let something else set up on it (like Volcarona, or even the recently banned Thundurus), but honestly, isn't the idea of using Offensive Pokemon, to find the best opportunity to let something come in safely, and start wrecking house? If there is even a problem with HO teams, then it will not be sorted by banning Deoxys-S. If anything, HO teams will gain a boost now that the #1 threat to them is banned, as they more than anything else hate hazards, Dragonite will take losing screens anyday to come in at 100%, when it is now pretty much guaranteed 1 DD, maybe even two.
Finally, in response to the last part of ToF's post: a big factor for me when using Deoxys-S is that it can use Stealth Rock to hinder Pokemon such as Dragonite and Volcarona, as you mentioned. If I see a Dragonite on the opponent's team, I will set up SR ASAP, even if means losing screens. Deoxys-S is high up there as a problem for those two certain mons.
I think there may be holes in what I have to say, but I feel that Deoxys-S is the scapegoat for a 'problem' that some people are having (likely with the BW metagame itself). The unpredictability argument has been summed up well by others. I'll leave this here for now, because there isn't more for me to add currently.
That and I might be getting people call me Nachos16 in the future.