Working with a customer in the past, we encountered a unique situation. One of my customer has recently done a server domain move to a new domain and found that busytime lookups for the other users from an old server, no longer worked. Original users at the old domain worked fine but the users at the new domain did not. We ensured that we were able to rebuild the busytime.nsf, validated that every domain value was 100% correct and it still failed.
To resolve the issue we did a number of tests and found that registaring the old domain server again but with the new domain name might be a option. After initializing the registration of the server we were prompted that an existing server already existed and did we want to update the existing document. We did so. This lead to a public key mistmatch between the server id and the Public address book. The only solution at this point in time was to replace the ID of the server with the newly registared one.
This did resolve the issue once and for all. The users at the new domain (i.e. Joe Smith/NewServer @ New Domain vs. Joe Smith/NewServer @ Old Domain) were properly visible when doing free time lookups from the calendar.
Please note, these are Notes domains and not Internet domains.