Oops, I forgot defun affected the global namespace.
Your last example is nice. I had to read the CLHS loop to have a clue about linearity of multiple termination clauses though :)
ps: funny, while googling I even found some lisp checker with a rule about nested defuns (## define-lisp-pattern nested-defuns)
http://www.cs.northwestern.edu/academics/courses/325/program...
I'd avoid recursive code like that as much as possible.
I'd write: