I have sketched an alternative proposal that does not need
uninternedness and doesn't change the semantics of symbols (as given
in R6RS, for example).

You can find it here: https://github.com/mnieper/gensyms

This proposal addresses concerns raised by Antero, John, Shiro, and
myself while allowing the use cases sketched by Daphne and Wolfgang.

As it happens, the proposal can be implemented portably, given a
random source (e.g. /dev/random). A native implementation that creates
random symbol names lazily would be more efficient, though.

Marc