I've certainly entertained ideas that are a lot weaker than NOID, for instance just have the peers exchange their sets of locators plus a cleartext cookie/context tag when the setup the state, and then do a RR check before sending packets to a new locator, but I've received pushback from folks that I wouldn't characterize as security geeks, that this would be too weak.
I don't think this is universally true. Certainly, this is too weak for TLS or IPsec sessions that can now be broken by an attacker, unlike before. But why would this be too weak for talking to Google over unprotected TCP/IP?
But perhaps it is time to writeup something like that and subject it to wider scruteny, combined with your suggestion below.