I have a 5th generation, 16GB iPod Touch that has iOS 8.1.0. I have a fairly recent version of iTunes.
I recently deleted over 1000 photos off my iPod and also deleted them out of the
Recently Deleted section. (Note: I also have the photo streaming thing turned off.) When I plug my iPod into my computer, it still says that I have over 2000 pictures that are taking up 4GB of space on my iPod!