Turn off Photo Stream on your iOS device so Photo Stream disappears. Turn it back on. For the pics that that "come back" and display, the delete confirmation message says they will be removed from all your devices (regardless of when they were taken). They are. All devices I used are iOS 5.1. I used this to clean up my ATV2 Photo Stream screensaver. I'm going to try and find the blog where this was solution was originally posted to give credit. Edit: Cleaned out pre-test details.