Nico,
"I have a problem, what's the solution?" isn't the easiest of questions to
answer. Please provide us with more information, including the query in
question, size of tables, indexes, source of your SP and the plan chosen.

As for a general answer, I can only say that avoiding NATURAL in plans
isn't the only thing that matters. Using too many or the wrong indexes can
slow down a query as well.

Set