How to merge by subtree while preserving history?

I have two separately developed projects (foo, bar) which I'd like to merge; the contents of foo should, initially, go in a subdirectory of bar.

I'm aware of two methods: moving (renaming) everything within foo into foo-dir, and then just pulling foo into bar.

This works beautifully, except that the big rename causes havoc w.r.t. to the files histories, i.e. git-log needs a "--follow" argument now, and "diff-tree" can't track changes when given the new file name. No good.

I've also tried the method described in [1], but it seems that all history is lost here (the text could point this out..) I've tried to "git pull -s subtree foo master" directly as well, but then it put foo into strange places (and lost the history).

So, I'm at a loss.  Suggestions much appreciated.

[1] http://www.kernel.org/pub/software/scm/git/docs/howto/using-merge-subtree.html