The problem is, there's two versions of xdelta: The original xdelta (v1.1.x) and an opensource xdelta (v3.0), and there's no easy way to tell which one you're patch is made with.
xdelta v1.1.x doesn't work with v3.0 patches at all, but makes tiny patches.
xdelta v3.0, in my opinion, is junk. It claims to be compatible with v1.1.x, but I've never seen it work and the patches it makes are considerably larger than the ones created by v1.1.x (400kb vs 20 something MB).