After much testing, we have reached the conclusion that there must be a restriction in how IIS treats CGI executables (possibly, penalizing disk access with security checks).
We tried launching console executables, that basically did the same than the CGIs (accessing the same FoxPro database), and the execution times were roughly the same (although they should have improved, but at least they were not worse).
Solution: Reinstall the new server with Windows 2003 Standard Edition.
Standard Edition (instead of Web Edition) allows Windows 2003 to use all four cores, and the 4GB of RAM. Windows 2003 and IIS6 don't penalize our CGI's. The execution time for a single CGI is now around 30% less than on the old server. Plus, the 4 cores allow us to handle the double of concurrent CGI's.
Thanks anyways!