This must be because you have tri-patches in your patch object. There is a small note about this in the help file, that patchdeform doesn't like tris.
So the solution is to try to change all tris into quads somehow.
I think this tri misery is because the U-V axis' would intersect there, or something like that.
hope this helps,
Laszlo Sebo