>I am wondering if it has something to do with the issue of the parameters being varchar() and the columns being char()
>
>If you make the columns varchar does that help ?

As soon as I removed the TOP clause, when using that particular field, based on its content, the speed was ok.

But, the DECLARE parameterized variables are only used in the SSMS environment. From my code, I simply pass any type of parameters as is. However, I have observed that declaring varchar as compared to nvarchar was in fact making a difference when that particular field is used. It seems to be related to the content and how SQL Server indexes it. In that particular field, it is a Char() but it only contains digits. Basically, the client created that field to be a sister field of the first one which contains also some letters. It seems the users are usually fast at remembering only the numbers of that main field so having another field containing only the digits of the main field was also good to include in the search.