Well it sounds like you've been "around the block a few times" on these types of issues.

I've taken over the responsibility of 20+ SQL Server boxes and have found a variety of issues/problems that would affect overall performance.

Things I look at are:

1) Are the Data, Logs & TEMPDB on RAID 1/0? or 5? and on separate LUNs?

2) Is tempdb split out into 1 file per processor? or something close to it?

3) I tend to throttle back memory usage for SQL Server allowing room for the OS. However with such a large machine I'm not sure you really need to do that.

4) You say your indexes & stats are up to date, it may benefit you to update them for the 1 table just to be sure.

I'd also have the boys in Network Operations double check the IO saturation levels and RAIDs of your LUNs. There is some magic that can be performed on the LUNs by introducing more cache as well as SSDs to increase their performance. There is no reason why things should perform poorly if all of the pieces are correctly configured.

Kurt