This patch produces the desired behavior for me and matches
the xemacs behavior when I use the following.

(setq display-buffer-base-action '((display-buffer-use-least-recent-window) (not-this-window . t)))

The explicit not-this-window is required to get display-buffer-pop-up-window
to trigger in a single window single frame case. It might be worth adding a note
to that effect to the docstring?

> Commenting out these lru-time settings will make
> it use as window for *bar* the window it previously used for *foo*.

This results in the behavior of the example matching that of xemacs.
With the lru-time option enabled the display multiple buffers case seems
to be served (I assume there is some other mechanism that can be used
to restore the previous window configuration in such cases that is not
included in this example).

The addition of lru-frames to decouple from reusable-frames is also good.
It produces the desired behavior in the context of multiple frames.

Many thanks!
Tom