"How can I find out which branch each parent was originally made on" -- ouch. Ive dreamed of automatically tacking on branch names to commit messages to solve this very issue.
And if the branch has been deleted, which typically happens after merging, then there's not much reason to know the branch name.
Is there something I'm missing here?
Most likely the branch names give you a good deal of information in working out why things have happened.
(assuming a non-fast-forward commit, where the branch is not really a branch because nothing happens in parallel)
I believe mercurial does this by default. Why not give it a try?