set-search can trivially be implemented as

(define (set-search set element failure success)

  (set-search! (set-copy set) element failure success))

An implementation which is based on immutable sets (as opposed to a hash-table based implementation), could do much better, though.

One may similarly argue for non-destructive analogues of the procedures bag-increment! and bag-decrement!.

Marc