iphoto: deleting photos from iPhone doesn't work
On your phone, open the Photos app and select Albums from the bottom.  One of the albums is Recently Deleted.  Once you delete the photos from there, and sync your phone, they should all be off the phone.  The Recently Deleted album appears to work sort of like a trash can for deleted photos and videos, but with a 30 day expiration.  If a photo or video isn't recovered from Recently Deleted within 30 days, then it is removed from the phone.