You should really mention Mew somewhere. Lead Mew looks like this:
@ Expert Belt / Lum Berry | Synchronize
Timid | 4 HP / 252 SpA / 252 Spe
- Stealth Rock
- Psychic / Psyshock / Thunderbolt
- Aura Sphere / Fire Plast / Flamethrower
There are a million variants possible, Jimbon even used a physical set with Tailwind / Explosion in the last two slots. Or you could run WoW or some status to cripple Deoxys. The point is, Mew can outspeed Deo-D thanks to its higher Base Speed, Taunt it, and then start to support the team in various ways (setting up SR / Tailwind, or boosting and Baton Passing out? That should work, too). You either forced out Deo-D or have a Taunted Deo-D that can barely touch you with SToss / Psycho Boost / whatever, while you do some great work for your team.