Random and Intermittent query performance issues when running on Windows Server 2008 R2 64-Bit

I have a product which I've been selling for many years and have close to 500 clients based on the Access 2003.  I distribute it with the Access 2003 Runtime engine.  I have long ago figured out how to distribute different versions for Windows XP vs. Vista vs. Windows 7 vs. Windows Server 2003 vs. Windows Server 2008 vs. Windows Server 2008 R2.  

In the past month or so, I have seen on a few new clients servers where a simple query of less than 10,000 records can run in about 1 second and then every once and a while the same exact query will take any where from between 30 seconds and 5 minutes (and possibly even hanging up my customer's server requiring a force quit of my application).  This behavior does not reproduce with their data files on my systems running MUCH weaker processing power and Windows XP.  

I have checked for viruses, removed all other software from the customer's servers - even reinstalled the operating system and replaced the motherboards and RAM.  No difference - the same issue continues to appear randomly and intermittently.  

These servers are powerful machines with 4 core xeon processors running at 2.67 GHz.  This is not a hardware issue.