The question is if serendipity really creates the thumbnail. On some image magick setups it could be that the user of the image magick creation code is different than the apache webserver. That's why I asked.
But your permissions sound fine, if the owners are the same.
But when deleting, did you check the option to remove all directory contents? Does the user you are operating with have hte adminImagesDelete privilege? Because the code of serendipity_deleteImage() does try to delete the thumbnail. Maybe you could look into the code and see why it does not unlink the images, please? The function code should be easy to understand, and since I cannot reproduce the problem on my machine it would really help if you could see why the image file doesn't get deleted for you?
If you don't want to modify the code, please mail here back again and I try to create the debugging code for you...
Regards,
Garvin