I know that if a worker fails to process a message off of the queue that it will become visible again and you have to code against this (idempotent). But is it possible that a worker can dequeue a message twice? Based on my logging, I seem to be seeing this behavior and I'm not sure why. I'm even deleting the message in between going go get the next message and it seems like I got it again.
You shouldn't be able to dequeue it twice. And if I recall things properly, even deleting it twice shouldn't be possible because the pop receipt should change after the second dequeue and lock.
As SilverNinja suggests, I'd look to see if perhaps the message was inadvertantly queued twice.