Right, I'm assuming that it would be relatively easy for someone on the team to convert a given image from colour PAL to high-res "scanned" black-and-white.

That being the case, I'd suggest first of all working out the "dot signatures" for all colours. I'd take a palette, e.g.
http://en.wikipedia.org/wiki/Web_color#Color_Table
and create a video, with each colour being on screen for, say, 10 frames. Convert this video to a series of black and white images with the dots.
Then build a database, matching "dot signatures" to each colour.

I'm unsure how the signatures will change (or shift) over the ten frames. Would ten frames be sufficient? Someone will have to enlighten me here. It may be that there are several different patterns for each colour.
This is the first "tricky" part - but if automatic coding cannot be achieved, the human eye can certainly pick out repeating patters, so could assist with building the database.

Once the database is built, I would suggest trying to use it to work out what a signature might look like for a colour shade that is not in the original palette, and then comparing it.

From the database to actually restoring lost colour footage is the final, and probably trickiest, challenge. I suspect that the scan quality will not be sufficient to recover small colour changes in detail (for example, eye colours), but I'm optimistic that at least a "basic" recovery is achievable, which will certainly be of help to any "manual" colour restoration work. The code would be similar to that of OCR: examining each frame bit-by-bit, looking for a dot pattern, working out what symbol (here: colour) that relates to, and exporting the result.

-- PhilipG