Photos deleted before wifi still appear in photo stream
As ksh above said, its because the photo is going into your recently deleted album, you should delete the picture from this album too, that'll stop the problem.

Theres currently no feature that allows you to turn off the recently deleted folder.