Consider a balanced tree that only exposes an immutable interface but uses destructive updates internally when rebalancing. In principle it would be immutable, though it wouldn't necessarily be threadsafe without additional work.
But I guess at this point we are starting to argue technicalities and it's getting quite outside the scope of this submission.
I'll just take a mental note with regard to immutable evidently being a lossy concept ;)