To help counter Deoxys, I usually do one of two things-
Carry a fast taunter. I've been toying with Cobalion recently, as some of you may know, it and easily outspeeds Deoxys and Taunts it. Pranksters such as Sableye/Whimsicott are also great ways to deal with the defensive behemoth. Lead Terrakion/Mixed Nape also occasionally carry Taunt, though it's relatively obvious when you send those in.
Carry a spinner. Deoxys-D really can't touch Forretress/Starmie without using HP Fire/Thunderbolt, which only the offensive set has. Forretress is great because it can spin and also Gyro Ball Deoxys-D to death. It can also Volt Switch on the Taunt to quickly switch in a teammember for free. Starmie, on the other hand, can spin, tank status, as well as chip down Deoxys's health with repeated attacks.
There are also many other smaller, yet still relatively effective ways to deal with Deoxys-D.
Trick- Trick it a scarf/band/specs, and watch it fail. It's great set up bait when it's locked into SR, but watch out for the Scarf set, as it'll just Trick you right back. Also make sure you have a pokemon that can take advantage of the momentary advantage, so you can set up.
Encore- pretty much the same as trick. It doesn't last as long, but doesn't smack you in the face when it fails either. If you're slower, however, you could be taunted, and that would be quite annoying.
Status- Toxic pretty much shuts Deoxys-D down, but again watch out for Taunt. There are relatively few common pokemon that can outspeed Deoxys-D and toxic it. I've seen people speed creep with Tentacruel, but it's really not worth it, as you lose a lot of bulk. With this, prediction is key, as you'd want to catch it on the switch and decrease the risks of backfire.
Just kill it- Any relatively strong super effective move can 2HKO Deoxys-D, as if it runs speed it'll lose bulk, and if it runs bulk it'll lose speed and you can try one of the above methods. U-Turn, Dark Pulse, and Shadow ball are all great ways you can eliminate the pokemon as a threat.
This is general for dealing with all hazard setters.