What is the optimal data structure for a tree of maps.
First of all, I think what you mean by "map" is a "dictionary" in TCS lingo. Second, I don't understand the phrase "ideally the lookup would still be $O(\log N)$", since in a dictionary the lookup takes O(1) time with various hash tables. Thirdly, you haven't stated whether the problem is static or dynamic; I'm assuming static.

The optimal complexity to this problem is $\Theta($predecessor search), e.g. $O(\lg\lg N)$ using van Emde Boas. This is optimal if you word size is $\Theta(\lg n)$; see http://people.csail.mit.edu/mip/papers/pred/pred.pdf for the optimal predecessor bounds.

The proper way to attack the problem is to build one global hash table and deal with the hierarchy separately for each key in the table. For one key $x$, we know the nodes where it appears. Consider an in-order traversal of the tree. The nodes where $x$ appears define intervals in this order. To determine whether $x$ is in the hash table of some node $v$, you have to ask whether $v$ stabs any segment as defined above. This is easily done by predecessor search, where we build a predecessor table for all interval end points.

For a lower bound, note that even one stabbing question is as hard as predecessor (see the reductions from colored predecessor search). Since the paper references above shows optimal direct-sum behavior for predecessor search, it means the algorithm described above is optimal for any ration between the number of nodes and the total number of keys.