Indexing billion domain names / strings
The standard solution is to build an index: a data structure that maps from search term to all of the records that match that search term.  Your index could be a hashmap or a B-tree, for instance.  In this case, the search terms are things like "google" or "facebook" or "facebook.com", and each one maps to a list of all records that match it.  Thus, facebook.com would be associated with two search terms ("facebook.com" and "facebook") and would be present in two of these lists.

You raised some concerns about this approach, but they are all manageable: 


Yes, search terms like "com" will match many records.  You should decide whether searching for "com" is useful or not.  If it's not useful, don't include that in the index: build a list of "stopwords" (e.g., com, org, etc.), and don't include any of them in the index.  For instance, you might decide that the TLD part of a domain name is not one of its matching search terms.
Yes, inserting or removing one record will require updating multiple entries in the index.  But this just isn't that big a deal.  Most domain names have very few components: e.g., "www.google.com" will require changing 2 entries in the index (assuming you have blacklisted "com"), which just isn't that big a deal.
Hash collisions are dealt with using standard methods for building hash tables and just aren't that big a deal.  Or, you can use any other data structure, like a B-tree.
No, this can't handle mis-spellings.  Mis-spellings are an entirely different problem, which require a range of different solutions, and you should ask a separate question about that (but first, study Levenstein distance, metric trees, and data structures for spelling correction and answering nearest-neighbor search in the Levenstein distance metric -- there are a bunch of questions on this site that are relevant).
No, there is no reason that the hash key needs to be 64 bits.  The hash key needs to be at least the number of buckets in your hashtable.


I suggest you read some standard resources on building indices, e.g., in database textbooks, and read about how search engines work.  Those topics are well-studied and those techniques will be applicable to your problem.