SQL Server salva "planos" de como executar código.

Se um procedimento armazenado for executado em um pequeno subconjunto de dados, ele será otimizado para um pequeno conjunto de dados. O oposto é verdadeiro para um grande conjunto de dados.

Há um bom OPTIMIZE FOR recurso em 2008, mas em 2005 você está preso com WITH RECOMPILE . Isso significa que ele será recompilado toda vez que for executado, o que, em alguns casos, é o ideal!