How is it possible to use Index Seek for LIKE %search-string% case?

Uri suggested the RECOMPILE hint because that would generate the different optimal plans depending on the parameter values provided.

I agree that OPTION (RECOMPILE) solves the issue. Another way of doing this (which seems to me more preferable) is to use OPTIMIZE FOR hint:

      IF LEFT(@Beginning, 1) <> '%'
                SELECT * FROM HumanResources.Employee
                WHERE NationalIDNumber LIKE @Beginning + N'%'
                OPTION (OPTIMIZE FOR (@Beginning = N'ZZZZZZZ%'));
        ELSE
                SELECT * FROM HumanResources.Employee
                WHERE NationalIDNumber LIKE @Beginning + N'%'
                OPTION (OPTIMIZE FOR (@Beginning = N'%'));

Anyway, this discussion is a little bit beyond the scope of the question because it was not about how to improve the SP - it was exactly what is written in the title and I received a comprehensive answer. Thank you very much.

---

Alexey