Shadow Pokemon: That's Pokemon XD you're talking about.
Go to the Snagem Hideout after beating Evice. I suggest something with good Defense because Gonzap uses X Attack a lot, and then Earthquake. Have a flying type with you to escape that. Just beat him away and he drops the D-Disk, then you can get to The Deep. If you still need Skarmory, I think Gonzap stays in the Snagem Hideout until you snag it.