I can't deny, this is pretty annoying. I've been out sick for a while, so right now this is what the deletion queue looks like:

I'll bet you a dollar there isn't a single user in that list that I'm not going to approve. Heck, I've only rejected 1 deletion in the entire time dev story has existed (I'm sure other employees have rejected more than that, but still - very very low false-positive rate).
That said... There aren't that many of these right now. That's almost a week's worth of queued-up deletions in that screenshot; it's just not that much of a burden right now. In comparison to the thousands of dev stories being created, this isn't worth making major changes to privileges to fix.
Visibility is the real issue here
The immediate problem is that there's a delay between the deletion and the dev story being hidden. Even if I'm not logged in, that escort service dev story you linked to is still perfectly visible, image and all; heck, if you signed up for an employer account you could even search for it (but... Guessing that's not the direction we should be headed for future revenue).
Fortunately, Roberta implemented a reasonable fix for this last week: when a moderator tries to delete a user with a dev story, they're immediately suspended - thus preventing them from posting more spam and blocking access to the dev story. There was an oversight there, in that it wasn't kicking in on spam destruction... But that's fixed now.
Long-term, we need better heuristics here. For example, if you've made no posts on the site (or better yet, all of the posts you have made have been deleted as spam), there's precious little reason to block deletion. Similarly, if the account is just a few days old, hasn't linked to anything on SO or a sane off-site code-focused service, it's probably not a valid story to begin with and we shouldn't be blocking deletion. She's out at the moment, but bluefeet will be doing some research here when she gets back.