読み込みでブロックするっつーことは stream が無効なわけじゃなさそうだね．
stream が buffering してんじゃない？ dc ないから bc で試してみた．pty
使えない環境なんで :stream 経由で．環境は sbcl 0.9.16 です．

CL-USER> (defun bc-example ()
(let ((process (run-program "/usr/bin/bc" '("-q" "-i") :output :stream :input :stream :wait nil)))
(unwind-protect
(progn
(write-line "x = 2" (process-input process))
(write-line "y = 29" (process-input process))
(write-line "x^y-1" (process-input process))
(finish-output (process-input process)) ;; これがないとブロックする
(write-line (read-line (process-output process))))
(process-close process))))

BC-EXAMPLE
CL-USER> (bc-example)
536870911
"536870911"