First, please make sure the query performs better with the index hint.
Second, when I write stored procedures I do my performance testing after executing DBCC FREEPROCAHE and DBCC DROPCLEANBUFFERS to ensure that it executes well on a "cold" server.
Third, and I do not really care for this, but to get a consistent execution time (if this is your aim) every time you execute, add WITH RECOMPILE to the sp definition.
Fourth, if your query runs unacceptablly long on a "cold" server, you need to tune the query as much as possible. People here love to rewrite code, so post your query and the execution plan and where the indices are placed and some one may help you out. See Brett's sticky at the top of the forum.
If one brings so much courage to this world the world has to kill them or break them, so of course it kills them. The world breaks every one and afterward many are strong at the broken places. But those that will not break it kills. It kills the very good and the very gentle and the very brave impartially. If you are none of these you can be sure it will kill you too but there will be no special hurry. Earnest Hemingway, A Farewell To Arms.