You're almost certain to want to use an XSLT to change the pages so
instead of refering to the frames, you'll refer to some SSI or <?php
include(); ?> statements, which will let you have the same
maintainability of frames but without the frames themselves (for
example, you'll change one file and the headers across all pages will
change).
Using an XLST, you should be able to process all of these pages in
about 10 minutes. XSLT would take an hour (at most) to write. The
problem would be running all of your pages through a program to make
sure they're syntatically correct. You'd want to run them through
something like tidy (
http://www.w3.org/People/Raggett/tidy/) or
Beautiful Soup (
http://www.crummy.com/software/BeautifulSoup/) first
to make sure your XML/HTML is proper, otherwise the XSLTs would
probably choke.
Finally, you'll probably want an internal person to work on any
alterations that require hand alteration.
If you get someone who knows what they're doing (you'd be well advised
to do that), it should not take them any more than a day (if you have
terrible pages).
Good Luck,
Eddie