It would work. My issue is largely depends on Gauche-specific characteristics, so I have to find a way to cope with.
The difference from set-search! and hash-table-update! is that those srfis don't expect those procedures being fundamental operators on which other procedures are built upon.
However, I agree that it's clean design to make mapping-search fundamental operator; many other operators can be built on top of it. And if you go with pure Scheme, functional implementation, mapping-search can be pretty efficient. And also it's desirable to have same or similar APIs to those procedures, so I support the way mapping-search is as it is, and efficiency concern is what implementations need to deal with.
Aside from the performance concern, there's a conceptual discussion on the design. For mapping and mapping-unfold, shall we adopt "earlier-takes-precedence" rule? It can be either way, but it's tempting to perceive that they apply mapping-set repeatedly in the order of the key/value pairs to populate the created mapping, which leads to later-takes-precedence rule.
One way to address that misconception is to add mapping-adjoin as you suggested, and explain mapping and mapping-unfold in terms of mapping-adjoin, instead of (implied) mapping-set. It's all about programmer's mental model, so if it is explained with the semantics of mapping-adjoin, earlier-takes-precedence rule becomes clear.