Is it possible to have 2 different thumbnail image styles for the same field?
You can put more than one filter on a preset, so it is possible, depending on the aspect ratio of the new and the old, that you can add a first filter that will remove the black bands and a second that will change the size.

Otherwise, you might try programmatically making image style change the aspect ratio of all your old images, deleting your old images, then copying the images in your changed image style directory to your root file directory. Image styles doesn't change the name of the file.

If either of those options doesn't work for you, you can create a custom field formatter that looks at the file id and decides which image style preset to use (as you suggested above except don't so this in the theme system as the new formatter would be available to any node view as well as in the views module). See: http://www.computerminds.co.uk/articles/creating-new-field-formatters-drupal-7