Good catch! The simplest way to do this would be to fix the check for equality and sort order for hosts. Add a __cmp__ rich comparison operator for the Host class that will only consider hosts equal if:
they have the same IP address (IPv4 or IPv6) AND
they have the same hostname or one of them does not have a hostname.
Then the host_pairs function could just compare hosts directly instead of calling get_id on each before comparing.