Alright, it took a bit, but it worked on one of my Maps0.dat files -- resurrected a correct mapindex.dat file for it!
Put fixmaps.exe into your map directory -- you may want to rename or copy the current mapindex.dat file since it will get overwritten. Run it (for you it may take an hour or more, and the progress bar is messed up, it goes beyond 100%!).
No guarantees! For use with v4.0 TF and up only (in case other people end up on this thread).
We'll see if it lets me attach a .exe file to a forum post or not.