Is "Lookup" checked for this TM in your project settings? It is possible to use a TM for concordance search only, although I can't imagine a scenario where I might actually want to do that.
I suppose it's good the option is there just in case.
[Edited at 2015-04-23 12:29 GMT]
All of the TMS in the project are "Enabled" and also "Lookup" and "Concordance" and the two subject specific ones for "Update".
Have you tried deactivating the project TM? That worked for me. Didn't notice any performance difference either, even with 100k+ TUs.
I shall try that eivind to see if it helps, but I can't imagine why it should make a difference.