Git noob question here (but someone who has been working on that noobishness for a year now): Can't you just rebase the branch you're on before trying to merge to another branch?
Rebasing is similar to merging. Instead of merging their code after your code, you are merging your code after their code. So if the two versions modify the same code fifty commits apart you'll have conflicts in both cases.