Lambda the Ultimate

I strongly believe that prolog-like unification (programming with holes) should be incorporated in every new programming language. One of my arguments is that unification is more general than pattern matching, and that unification is just as natural as pattern matching.

In contrast, I find the unification of two sets hardly intuitive. Set unification is not only non-intuitive but also NP complete. Still, I believe that set unification, as a first class operation, is an interesting programming construct.

Actually, I'm more interested in the unification of multimaps because they extend sets. My intuition also tells me that multimap unification can be made more efficient in most use-cases.

I'm not sure however. Are there any unification 'theorems' that I should consider that counter my intuition?