SQL Server sparar "planer" för hur man kör kod.
Om en lagrad procedur körs mot en liten delmängd av data kommer den att optimera för en liten datamängd. Det motsatta är sant för en stor datamängd.
Det finns en trevlig OPTIMIZE FOR funktion 2008 men 2005 har du fastnat med WITH RECOMPILE . Det betyder att den kommer att kompileras om varje gång den körs, vilket i vissa fall är mest optimalt!