One further improvement might be on the accept path, to do a check in
  the reverse direction against the routing table (or whatever) to make
  sure the envelope address matches the expected source of the internal
  address.

That depends on what you are trying to do.  In my application (Mobile
IP), the tunnels aren't symmetric, so the fact that there is no route
pointing back is irrelevant when accepting a packet (much like how you
don't check incoming ethernet packets to see if you have an ARP entry
back to the IP src of the packet :-).  I can see that such a check
could be useful in some circumstances, depending on the policy one is
trying to implement.  So perhaps LINK2 could control that or
something if a particular need is articulated and found to be common.

  Exactly what I was thinking, which is why the routing table doesn't
  seem such a bad way of representing this (perhaps in some of the
  alternate forms you discussed).  Perhaps, like stf(4), it might better
  be implemented as a separate interface.

I realized that the gateway route is probably used because the gateway
sockaddr is passed to *_output().  But I suppose gif(4) could snarf
code, conceptually at least, from if_ethersubr, to do an arp-like
lookup for the given dst to a 'llinfo' sockaddr with -ifp gifN.

I hesitate to have a separate interface because aside from a few lines
of code that choose a different destination address, and a line that
declines to make the source address check (and now, probably the
registration into ip_encap), really very minor and easy to understand
changes are needed.  It would be also quite easy to make a kernel
option for GIF_MULTIDESTINATION.

With stf(4), rules about how to map 2002::/16 addresses to IP
addresses are built-in, as well as anti-spoofing valid address checks,
and these things are quite RFC3056 specific.  So it really does seem
like a different beast.

    Greg