Using Actions may help, and is a good strategy if you can get it to work (Actioning several Find Font commands for all the different type styles you have).
Another method, if you're game, is using a text editor to edit the documents. It's a bit more risky, but could certainly blast through thousands of documents in a very short space of time.
Here's some steps that might get you started.
Duplicate all the documents you wish to edit. I can't stress this enough... there's a very good chance you'll do some serious damage if you're not careful, so you'll want to work on copies.
Depending on the text editor you're using, you may need to rename all the files to be .txt rather than .ai. If you're using OS X, Apple's free Automator app can do this (it's in your Applications folder already). The Automator Action you want is Rename Finder Items
.
Open up one of the documents in a good text editor that can Find and Replace across documents. You'll probably want something like BBEdit, Coda, Espresso, TextMate or a similar editor that's for programming. I generally use Code for this type of thing.
Find the portions of code that contain the font info. Adobe Illustrator .ai files contain some XML that's probably the bit you'd like to change, so they should be pretty easy to work with. I just saved a document with some text in it. Here's some of the XML in my document that shows the font (you may need to change several places).
<rdf:li rdf:parseType="Resource">
<stFnt:fontName>MyriadPro-Regular</stFnt:fontName>
<stFnt:fontFamily>Myriad Pro</stFnt:fontFamily>
<stFnt:fontFace>Regular</stFnt:fontFace>
<stFnt:fontType>Open Type</stFnt:fontType>
<stFnt:versionString>Version 2.006;PS 002.000;Core 1.0.38;makeotf.lib1.6.6565</stFnt:versionString>
<stFnt:composite>False</stFnt:composite>
<stFnt:fontFileName>MyriadPro-Regular.otf</stFnt:fontFileName>
</rdf:li>
- Rename all your files back to .ai.
You'll have to experiment a lot. You'll probably want to edit one document to see what the before and after look like, then try to automate it with one or several Find and Replace actions.
Once you have it working, you can apply that across all your files (remember, on the copies, not the original files!).
Is that going to work? Is it worth your time? Maybe yes, maybe no. It depends if this is a regular thing you need to do, how comfortable you are with the method and how many files you have.
Please note that changing the font will likely move elements and text may be significantly reflowed.