It unfortunately looks like these artifacts are encoded into the video, ie. a bad NTSC->PAL transfer. I know because when I went to change the framerate of the video in VDubMod it was already 25fps. Similarly, with Womble I inserted one of the scenes and it changed to 25fps straight away.

Oh, and MeBeJedi, as for my setup:
I'm using an AMD Athlon XP 2600+ (1.92Ghz) with 768MB of RAM, running Windows XP SP2 on a hard drive set to NTFS.
Max_Rebo:
Here are shots from each of the sources to compare the bar sizes:
Scene from the movie
Scene from Disc 1's Deleted Scenes
Scene from Disc 1's Deleted Scenes after being 'anamorphicised' like detailed
Scene from Disc 2's Deleted Scenes
If you could enlighten me Max_Rebo, how can you calculate the correct cropping/resizing numbers for the different aspect ratios? What I mean is, is there a table that tells you the different values you must use when you want to crop/resize letterboxed video to make it anamorphic. I think I've seen something like that before for NTSC format, but never for PAL. For example you said to resize to 720x428, then crop 125 from either side - where did you pull these values from?
I've also reripped the movie to my hard drive with 'no-splitting' enabled. I now have a "Stream Information" text file, a small IFO file, an M2V of the entire movie and an AC3 of the entire movie. Would it be better to re-rip the deleted scenes like this? Should I have them as separate scenes or rip them together as one long M2V & AC3?
Here is some brief info on the scenes from Disc 2 (this is mainly for Max_Rebo):
1. Extended Fanty & Mingo (2:15)
Fanty & Mingo have some more lines. There's a fun one "Me and Fanty is greedy. You could set your watch by our greed, it wavers never".
2. Extended Mal Inara Wave (2:16)
More of the conversation between Mal & Inara over the wave. One noticeable addition is Inara asking if Mal is wearing pants.
3. Extended Mal & Operative in Companion Training House (0:49)
The Operative has a tiny added bit of talk. He tells Mal how River is his 'purpose'. It helps the extended Coda from Disc 1 make more sense/fit better.
4. Mal & Inara Shuttle Improv. (0:50)
Mal talks to Inara on the shuttle flight back to Serenity about the Operative. This mainly shows Mal afraid that Inara will tell the others he was beaten up.
MeBeJedi & Max_Rebo:
I guess, the question now is, is there any way to 'fix' these deleted scenes? It appears that the artifacts are less prominent in the scenes from Disc 2. Would it be better to upconvert the NTSC versions of the disc 1 scenes if there isn't a reasonable way of getting rid of these artifacts?