I don't want to jump to conclusions, it's too late so chances are high
that I'm missing something, plus I don't have all those
implementations installed to try...  So can you check how your
configuration runs the simple memoized version?

I assume that gambit and bigloo provide `eq?' hash tables...  The
interface shouldn't be difficult to mimic if it's different -- there's
make-hash-table, (hash-table-put! table key val) and
(hash-table-get table key failure-thunk).  A nice point is that an
efficient `eq?' table is enough since the simple code only calls
itself on cdr's of l.

;;--------------------------------------------------------------------
(define (memoize2 f)
  (let ((table (make-hash-table)))
    (lambda (x y)
      (let ((table2 (hash-table-get table x
                                    (lambda ()
                                      (let ((t (make-hash-table)))
                                        (hash-table-put! table x t)
                                        t)))))
        (hash-table-get table2 y
                        (lambda ()
                          (let ((r (f x y)))
                            (hash-table-put! table2 y r)
                            r)))))))
(define (msubset l n)
  (cond ((<= n 0) '(()))
        ((null? l) '())
        ((= n 1) (map list l))
        (else (append (let ((hd (car l)))
                        (map (lambda (lst) (cons hd lst))
                             (msubset (cdr l) (- n 1))))
                      (msubset (cdr l) n)))))
(set! msubset (memoize2 msubset))
;;--------------------------------------------------------------------