この pairs の実装はどこが間違っているのかという問題です．
(define (pairs s t) (interleave (stream-map (lambda (x) (list (stream-car s) x)) t) (pairs (stream-cdr s) (stream-cdr t))))
実際に走らせてみたところ，無限ループにハマってしまいました．
(pairs integers integers)
そうか! interleave の段階では遅延評価されないので，interleave を呼び出す段階で，pairs が呼び出される．integers は無限ストリームだからこの呼び出しが止まらず，無限ループになるわけか．
