Before going any further - which version of VFP are you using?

>Yes, I've tested different workstations/server combinations on different networks, etc. Same result.
>I've tested XP to XP, Vista to Vista, XP to Vista, Vista to XP, XP to Server 2000, Vista to Server 2000, XP to server 2003, etc. They all have the same kind of performance numbers.

That's very thorough! One question: are all of those machines actual, physical computers or are any of them virtual machines running in a hypervisor somewhere? I'd hate to think that what you're seeing might be an obscure issue with the way a hypervisor handles inter-VM SMB file- and record-locking.

If you've tested on different physical networks I assume we can rule out any issues with switches, DNS servers etc.

>There has got to be something I'm overlooking that explains why:
>The same workstation accessing the same data across the network will perform this routine in 7 seconds as long as no other workstations have the database/table open. As soon as another workstation opens the database/table, even if the other workstation isn't actually doing anything, it makes the routine on the first workstation slowdown from 7 seconds to 35+ seconds.
>Another note: in a peer-to-peer environment, the "server" computer that hosts the data does not slow down when another computer opens the data; the "client" computer (as mentioned above), however, does.
>
>I'm going to try and drill down using the coverage profiler in my compiled .exe to figure out what is actually taking so long. Any tips on a good coverage profiler add-on?

I was just going to suggest, as a SWAG, checking into any oplock (opportunistic locking) settings that may have been changed on your servers or workstations. When searching the threads here on "oplock" I found a very interesting branch of a thread, starting at Message#1293684 which may be directly applicable to you.