I'm considering running a Deathwatch game because i think that some of my people would really enjoy it. If I go down that road, I'd like to at least start off with a pre-written scenario because a good pre-written story is easier to pull off than coming up with one myself especially when the characters will be new and I suspect not particularly well fleshed out.(Yes the very best games have come from carefully interweaving the stories of all of the characters, If things go well I'll twist the story to be more centered on the specific characters later).

So, of the scenarios available, which would you recommend? (Most of the perspective players played three or four sessions of deathwatch four years ago, some of the perspective players know and love the setting, some of them are mildly familiar with and tolerate the setting).

Final sanction is a decent intro. A nice combo of combat, investigation, and strategy. Genestealers actually scare space marines so you don't run into the "invulnerable unless I make them them a horde" problem.