For what it's worth, you might want to look at Jeffrey Siskind's SCREAMER, which provides nondeterministic programming (with backtracking) for Common Lisp. Of course, this does not include objects, but it would probably be worth a cross-reference.
best, r