>>Michel, is this one large query, or a procedure with multiple steps / queries?
>
>It is one query.

OK, might be premature to make a suggestion, but sometimes breaking up into multiple steps can help.

I just took a query that was running way too long and did a "divide and conquer". Grabbed a chunk into a table variable and then did a subsequent query from that - brought the time down significantly. Not saying that would necessarily solve your problems, but something to at least consider.