Alternatively, we could move the 'Location' settings from the main block administration page to the blocks' individual configuration pages, and provide one selection menu for each theme. It's somewhat tedious to administer but it would solve most of the problems.

I am okay with this approach too. Regards, Kobus