Ok, let's think you already know the problem. Now I'll explain how DO handles this:
1. DO always returns correct type of any Entity. I.e. you will never get an Animal instead of Dog. So if type of some Entity isn't known (below I describe what this mean), but we must return its instance, we'll go to the database for it. Such a query will fetch all non-lazy fields of this Entity in addition to its type.
2. Our LINQ query translator is designed to pull the informational about type of any Entity or Key you're going to materialize through the whole query. Currently this information is stored in TypeId field, but later we'll allow you to use custom type discriminators.
3. We maintain LRU cache of Key objects. Each key caches the type of Entity it belongs to. Default size of this cache is 16K Keys, and it contains only those Keys which types are precisely known (but we don't cache Keys of hierarchies consisting of just a single type). So in fact, we cache ~ 16K types of entities we used most recently. This means we can materialize the entity without its type lookup on subsequent access attempts - even in different Sessions.
4. Key comparison (Key.Equals, etc.) is optimized for presence of such cache. Different Key objects may correspond to the same key, but since some Keys can be cached, there can be a single instance of such keys shared across multiple Sessions. So first we compare keys by references, then we compare their cached hash codes and only after this we compare the content. In fact, Key comparison happens quite fast.
5. As you might see, we imply type of any Entity can't be changed during application lifetime. The same is correct for .NET objects, as well as for objects in many other languages. Although this is not always correct for objects stored in databases :) The only way to properly handle entity type change in our case is to clear domain key cache. I think this is acceptable, because this is either what really never happens, or happens quite rarely.
That's it ;)