-U turn lead + magic bounce
-Band/Specs/SE moves that can 2hko, Gengar, Garchomp, Tyranitar, etc
-Faster taunt users, Keldeo, Terrakion, Gliscor, etc
-Mons to set up on it, such as gengar
-Rapid spin user - (the Gengar switch in is SO predictable) (u can even lead with donphan.. of all pokemon... and spam rapid spin :)
-Team that doesn't mind SR
Ok, here we have 6 "solutions" to deal with deoxys. I'll ignore the team one, because that's pretty silly and you'll still care about spikes. U-turn lead + Magic bounce is, as Bays said, inefficient in the requirement of two pokemon to break one hazard setter. I know this is grasping at straws and fills the moveslots, but skill swap is also viable. Let's take that off the table.
So, 4 methods: 2HKO with powerful moves, faster taunt, set up, or rapid spin.
Assuming deoxys has Spikes, SR, and Taunt, that means it has open one move and one item. This means it can beat two of these four strategies.
Let me break down rapid spin first: I'll focus on Donphan, as you mentioned that, as well as starmie. Let's say you have Donphan: the "so predictable" gengar switch results in you doing what? Stone edge? Donphan is pretty starved for moveslots as is, I'd say the most common one would be EQ+Rapid Spin+SR+Roar/Ice Shard. Even so, gengar can get a switch in for free, set up substitutes and disable your move to hit it with, unless roar in which we really got nowhere. It can also hit Donphan for some damage. Leading with donphan? If deoxys has psycho boost, then you're done. However, I think this is rare and donphan is better handled with gengar anyway.
Starmie: this has really been covered already, if deoxys has thunderbolt then you're in a bad position, meanwhile you can either attack or spam rapid spin, spamming rapid spin leaves you open to gengar, as I wouldn't think starmie can OHKO it. Attacking lets deo get a hazard off, and then if you spin they can just switch to gengar. There's lots of evidence already as this has been discussed a lot.
Moving on, we have 3 methods: 2HKO, fast taunt, or set up. Setting up, with gengar as you say? Deoxys will throw out all hazards in your face while you put a substitute up and won't really care if it dies. Boosting sweepers, such as volcarona or dragonite, can still be crippled by a twave.
Now, fast taunt. This can be beaten 2 ways: Magic coat and mental herb. Magic Coat will take the place of the fourth move and allow deo to taunt your taunter, and then set up. Mental Herb accomplishes the same result.
2HKO Deoxys: All made or broken by red card. Deo will at best get SR up already, and if it has red card then luck will result in a random switch, most likely resulting in another layer, maybe 2.
So, as I said before, we have an open moveslot and item slot on deoxys, as well as 3 strategies to shut down deoxys, excluding rapid spin, because I'm really not convinced it keeps deoxys from doing it's job and there have been lots of arguments made on it (it's also screwed by red card).
Setting up is counterd by a twave, 2HKO is countered by red card, fast taunt is countered by magic coat and mental herb. Assuming deoxys has a random combination of these four items/moves, excluding both magic coat and mental herb together, it has a 66% chance of beating things that are meant to shut it down. That means 2/3 times deoxys will be in a winning position against its "counter" methods. It may even get up SR against the one it is not prepared for.
That seems unhealthy to me.
The bottom line is that there are many "viable" strategies for beating deoxys, but it only needs to run one move/item to ruin each one. While deoxys can't beat all of them at the same time, it has a VERY high chance to beat the one you're using, and it's extremely pointless to use more than one of these strategies to beat deoxys; if anyone is going to say that this should be a step taken then look up the definition of overcentralizing.