I'm pretty sure this is a negative result of parallelism.

I think setting your server-level MAXDOP to 0 means that you're letting SQL Server manage it instead of specifying a value. I might be wrong on that. My guess is that you have more than 26 cores.

you could also ask them to specify the MAXDOP query hint.

more info here on that setting: http://msdn.microsoft.com/en-us/library/ms189094(SQL.90).aspx

~BOT