> We have apps that use very large tables in VFP. (Tens of millions of records).
> We open the tables and scan through them to process each record.

You need to use SQL language for data scanning/selection. As I understood, you have a simple file server with
classic DBFs. If you are not going to rebuild your database into MySQL etc. try to change SCANs into SELECT-SQLs.
The speed will increase incredibly.