> Conceptually, it does this by constructing a new copy of the result for every addition, since conj is not destructive
That's not how persistent data structures work
http://hypirion.com/musings/understanding-persistent-vector-...
> why does efficient set union of two collections require one of the two collections to support fast membership tests
I haven't thought much about this but it seems intuitively true to me. You want to take the smaller set, and add each item to the larger set if it doesn't already exist. That last part is why you need a fast membership test.
If you're still unconvinced, try loading up two similarly structured database tables with a million rows and get the union of them (with and without indices). The indexed one will be orders of magnitude quicker.