Any chance you can depend on having century available? ... if so you might be able to impute the pattern.

I haven't thought about that much though. For instance how would you impute..

12112003

in Mexico that would be 11/12/2003 (mm/dd/yyyy)
in Seattle that would be 12/11/2003 (mm/dd/yyyy)

or what if the underlying pattern were mmyyyydd

01192001 --> 1/19/2001 or 1/1/1920

If you can't find some pattern or at lease some upper and lower bound for years that you can live within, it could get really tricky! Good luck!