Hi. As of now, when paredit is used for REPL buffer, history doesn't work because closing parentheses are inserted automatically. E.g. I type (| at the point): (format|) and press M-p, but nothing is found because the whole input is used. I think the reasonable way to fix this is to use the portion of input between slime-repl-input-start-mark and (point) for history search. The attached trivial patch does just that. I hope such behavior will not interfere with anyone's habits as when paredit is not used M-p is usually pressed when the point is at the end of input. When the point is at slime-repl-input-mark or before it, the old behavior is used.
Ivan