Just to throw an extra potential spanner in the works, some PAL releases are based on bad NTSC -> PAL bad conversions, which results in that sort of interlacing. Many of Tartan's asian DVDs releases in the UK are shoddy PAL conversions from an interlaced NTSC master, rather than being taken from a true PAL transfer. It means some of the original NTSC interlacing is retained, and can also result in some weird motion/speedup problems where the video appears to be dropping or doubling frames because of it.

Looks like the deleted scenes you're using could be suffering from the same thing.

If this is the case, I'm not sure how fixable it is. Best thing to do would be to post a sample of the video and let one of the technical wizards like MeBeJedi to take alook at it.