Where are PuTTY host names stored

All PuTTY settings are stored in the registry in the case of windows, more exactly in: [HKEY_CURRENT_USER\Software\SimonTatham].

Host names, in your situation, can appear like that due to DNS server (or whatever is handling your DNS naming) bad configuration. some of the anomalies can be host-names that appear for various IP addresses even if they do not use that address anymore or that appear to have multiple IP addresses.

Just the same, a DNS server can have aliases pointing to host-names.

Windows will use it's builtin name resolution, so you will not find plain strings anywhere. Its most likely stored in DNS or reachable with mDNS.