Ok, solved with a little more help of: HTTP error (422 - Unknown): Validation failed: Name has already been taken - #7 by marcelo.messias
There it was solved by simply manually deleting the corresponding blocking data entities. So I did this as well and was then able to delete the host.
So first I identified the odd host:
sudo -u postgres psql foreman -c "SELECT id FROM hosts WHERE name = 'odd.host.name';"
Then I tried to delete the host:
foreman-rake console
Host::Base.where(id: [16]).destroy_all
This spit out the foreign key constraint which blocked the operation. Then in my case I had to delete from the following two tables:
sudo -u postgres psql foreman -c "DELETE FROM host_puppet_facets WHERE host_id = 16;"
sudo -u postgres psql foreman -c "DELETE FROM host_puppet_facets WHERE host_id = 16;"
Now the above mentioned delete operation from the rake-console was successful.