diff --patience uses a different algorithm that works to optimise the diffed number of lines (it's less efficient though), which will probably solve your issue (the way the standard algorithm works is to essentially find common features on a first-come-first-served basis.