Okay, I've put together something based on Hash-Array Mapped Tries that implements an ordered list with unique elements. The code and a README file with caveats are here:
I wrote it to match my own code base, but it could easily be adapted to be more portable, to match Marc's or John's proposed API, and to use a standard unit testing framework.
So far, I haven't used this code as part of any other system.
Marc, if you'd like to prepare a SRFI around this or any other implementation, I'd be happy to publish it. Thanks for the inspiration.