Right now the delete message is rejected with a flash message that says which hosts are still connected to it.
I am thinking on adding a more permanent warning message to the edit page, that will warn the user that the hostgroup is used in multiple organizations/locations.

I think this issue should be marked as resolved.
The original issue was related to an error caused by deleting a hostgroup that is still in use in a different taxonomy, and as far as I understand that issue does not occur in current versions.
Adding a warning to indicate a hostgroup is shared across multiple taxonomies is a bad idea in my opinion for several reasons:
1. Displaying a warning message indicates there is something wrong with sharing across taxonomies. This is a valid use case- for example, a base hostgroup that is used to set some common attributes across several locations.
2. Hostgroups are not unique in this matter. For example, templates can also be shared across multiple taxonomies. If we add warnings, we should add them across all resources that may be shared (which is almost all of them) - causing cluttered UI.
3. If a hostgroup contains taxonomy-specific settings, then it should be scoped only to the relevant taxonomy. If a user mistakenly connects it to other taxonomies, well, I think PEBCAK. If you want to use most of the same settings for another taxonomy - that's what the clone button is for.
4. In some cases this may leak information to a user that they are not supposed to know, i.e. if they only know about one organization they may learn potentially sensitive information about others (for example, that another organization uses the same setup - and possibly root password - they do).