Why is SQL running the same query longer from another connection? Here is the issue overview: Why does my stored procedure run faster when executed localy vs remotely?

Dont jump to any conclusion just yet, let me explain what I mean...

Here is the setup:
A Windows 2008R2 (correction: 2003) application server executes a stored procedure that performs some action, (what its doing is really important at this point in time). This stored procedure is executed on the SQL server over a TCP/IP connection to the database server. The DB server is physicaly located right next to the application server, and they are connected to eachother via 1GB NICs to a 1GB Switch. The DB server is running SQL 2005 SP2 Enterprise Edition, and has 16GB of memory and several vLUNS striped across 48 15k drives in an HP-EVA FC connected SAN. From all indicators thus far, there are no I/O, Mem, or CPU constreints or limits being hit. Trace Falg 1118 is on and TempDB is split across 8 file on their own vLUN. Data, and TLogs also have their own vLUNS too.

So, here is what I am seeing:
Using SQLCMD on the database server, with SQLProfiler running from the same DB server, I can execute the stored procedure and I see that the execution starts immediatly, and compleats with a durration of about 2,100ms with an IO of about 1200. 

Using SQLCMD on the application server, with SQLProfiler running from the DB server, I can execute the same exact stored procedure, with the SAME exact parameters, and I see that the execution starts immediatly, and compleats with a durration of about 110,000ms with an IO of about 1200. 

The query results in 1 row, with 4 columns [INT, INT, VARCHAR(50), VARCHAR(100)]

ASIDE:(I know the query is a train wreck, this is a regulated system and I cannot change it on a live prodution server, so please dont make any sugestions about doing so. The next version has been rewritten to be better.)

From everything we can see, there is no reason that we should be seeing differances like this, but what is heppening is the .NET application that calls this query from the application server is timing out waiting for the responce. 

We have checked locking and blocking, WAIT states, Query plans, IO contention, CPU contention, MEM contention, NETWORK saturation/utilization, performed indexes rebuilds on all indexes, updates all stats, and a hand full of other items, but haven't come up with anything that points to why this is happening. 

Please ask more questions if you have any, make recomendations as you come up with them, and depending on the impact (remember this is a production environment) we will try them and respond back.

-Thanks!
-Chris
This is not a networking issue (though that is tempting).

This is almost certainly "noise." What I mean here is that you need to run this operation perhaps 100 times on the db server itself and from the app server, preferably over a span of 2 hours or so (or more).

What I strongly expect you will find is that at certain times it runs fast on either/both systems, and at certain times it is slow no matter where it is initiated.

E.g. the SQL workload is what you are actually measuring, not the network.