mh-e does need an MH implementation. emerge -pve mh-e does not show such an implementation. Solution: make mh-e depend on mail-client/nmh.
Unfortunately the problem is more complicated. The mh-e package is also used by a number of other packages. For example, app-xemacs/net-utils depends on mh-e because xemacsbug.el tries to access 'mh-e-user-agent. The implication of this is that people trying to emerge net-utils would also get nmh installed, even though they would never use it. The same is true for a number of other packages. Normally this would be solved by including USE flags, so we could perhaps add a nmh USE flag to app-xemacs/mh-e.