Isn’t that what the hard cropping option is for? You even have it documented in the KB:
http://support.swiftideas.net/knowledgebase/product-image-quality/
Making it NOT hard cropped and regenerating the thumbnails obviously screws everything up even worse, while marking them as hard croped and regenerating thumbnails alleviates some of the issue. However, the the images are obviously not being cropped consistently.
I don’t think this is an issue with my image sizes, and fixing it shouldn’t require editing every single one of my product images by hand and re-uploading.