One of my clients recently had a problem where a query with a semi-measly execution cost of .3 was taking 25 seconds to return. Worse, forcing the query to use a suitable index (instead of the PK with accompanying bookmarks) had a cost of 4.8 and returned instantly. Moreover, the query taking 25 seconds was only iterating over a couple of small tables (< 70k rows each) on decent hardware. There was really NO reason for the query to take 25 seconds - yet it was consistently doing so.

To troubleshoot I did the following:
a) updated statistics explicitly on the table in question (nightly statistics updates were already in place)
b) rebuilt indexes to remove fragmentation.
c) corrected/updated storage info using DBCC UPDATEUSAGE. (Usage stats were pretty out of whack - the table had a number of indexes showing that they were only 2-4 pages in size, while they were actually 200-400 pages in size. Imagine my disappointment when updating this didn't have ANY impact on that phantom 25 seconds.)
d) recompiled the offending sproc
e) double-checked to ensure that data type coercion issues weren't hosing an index or something similar...
Then finally remembered (with help from Wally) a similar problem I had a few years earlier with HT and some unexplained proc problems. As a simple test, I tweaked the single select within the sproc to use OPTION (MAXDOP 1) to check to see if HT might be the issue - and the sproc returned instantly after a recompile. At that point I knew that I either had HT processors, or a nasty, ugly bug going on with the way that parallelism was being handled. A few minutes later confirmation came back: HT processors. (Note too, that this SQL Server in question has been patched for HT support.)

So, HT procs.... I can easily disable them using the bios. Trouble is that they're nice on smaller boxes (I think the server in question only has 2 physical procs). But when they occasionally add a phantom 25 seconds to a core query.. that makes keeping them hard.  Not sure what I'll recommend at this point, but it looks like HT might have to go.